a.) For which $n>2$ is there a set of $n$ consecutive positive integers such that the largest number in the set is a divisor of the least common multiple of the remaining $n-1$ numbers? b.) For which $n>2$ is there exactly one set having this property?
Problem
Source: IMO 1981, Day 2, Problem 4
Tags: number theory, least common multiple, algebra, polynomial, IMO, IMO 1981
29.10.2006 22:38
13.06.2007 05:09
Let $A: (a, a+1, a+2, \cdots, a+n-1)$ such that $a, n \in \mathbb{Z}^{+}.$ In other words, this is our desired set. Lemma: $\exists A$ such that $A:{a, a+1, a+2, \cdots, a+n-1}$ where $a, n \in \mathbb{Z}^{+}$ and $a+n-1|lcm(a, a+1, \cdots, a+n-2)$ if and only if $(n-1)! | a+n-1.$ If we take the polynomial $P(a) = a(a+1)(a+2)\cdots(a+n-2)$ and find the remainder when divided by $a+n-1,$ we simply find $\frac{a+n-1}{P(-n+1)}.$ If this remainder is equal to zero, then we can solve for $a.$ If $a$ is an acceptable value, we can then construct an appropriate set $A.$ Note that $P(-n+1) = (-n+1)(-n+2)(-n+3)\cdots(2)(1) = (-1)^{n-1}(n-1)!$ $\Leftrightarrow \frac{a+n-1}{P(-n+1)}= \frac{a+n-1}{(-1)^{n-1}(n-1)!}$ Thus, if $(n-1)!|a+n-1,$ we have that there exists a valid set $A$ with cardinality $n.$ $\blacksquare$ We will now commence proving parts A and B; this lemma will be used in both parts.
Could someone grade me out of seven points and give me style points as well? I would really appreciate it
17.02.2022 04:34
Basically for a set to satisfy the property, the largest number must not have any prime powers that are not divisible by any of the other $n-1$ numbers. For a given $n$, let $k_n$ be the largest element. The answer for part $a)$ is $\boxed{n\ge 4}$. Part A1: Show that there is no such set for $n=3$. Suppose there was. Then the largest element must not have a prime power that is not in the first two elements. So all of it's prime factors are either divisible by the first or second element, which implies they must all be $2$. But $\nu_2 (k_n)>\nu_2 (k_n-2)$ in this case, a contradiction. $\blacksquare$ Part A2: Show that there always exists a set for $n\ge 4$. We let $k_n=\prod_{i=1}^{x} p_i^{a_i}$ for nonnegative integers $a_i$ and $p_i$ is the $i$th prime. We let $p_i^{a_i}<n$ for all $i$. It's clear that this works because any $p_i^{a_i}$ divides some other element as $p_i^{a_i}<n$. Such a product of prime powers exists for $n\ge 4$ because the product of all distinct primes less than $n$ is always greater than $n$ (not that this is not the case for $n=3$). $\blacksquare$ The answer for part $b)$ is $\boxed{n=4}$. Part B1: Show that $\{3,4,5,6\}$ is the unique set for $n=4$. Again let $k_4=\prod_{i=1}^{x} p_i^{a_i}$. Clearly all the $p_i$ are either $2$ or $3$. The highest possible power of $2$ is $1$ and the highest possible power of $3$ is also $1$. But we also need $k_4\ge 4$, for the set to contain only positive integers. So we must have $a_1=a_2=1$. Thus, $6$ is the only possible value of $k_4$. $\blacksquare$ Part B2: Show that there exist more than $1$ set for $n>4$. Let $k_n=\prod_{i=1}^{x} p_i^{a_i}$. Let $p_x$ be the largest prime less than $n$. Then set all $a_i$ to $1$. This works as $k_n=\prod_{i=1}^x p_i>n$. Now since $n>4$, we can also set $a_1=2$, which also works. $\blacksquare$