AoPS Academy
be a positive integer such that divides the sum![\[
1 + \sum_{i=1}^{n-1} i^{n-1}.
\]](http://latex.artofproblemsolving.com/e/2/d/e2daf7800da3f984cd761ed1fecf10083444db25.png)
Prove that is square-free.
,such that the inequality 
holds for all positive reals 
and for every positive real 
, there exist positive reals 
, such that the equality holds.
be a triangle with 
. The tangent to the circumcircle of 
at 
intersects 
at 
. The angle bisector of 
intersect at 
. Suppose that the perpendicular bisector of 
intersect 
at 
, respectively. Show that 
?
, and the sum of the roots is 
. So we need to find a combination of integers that multiply to and add up to . Let's call the roots of the equation p, q, and r. From Vieta's, we get that 
and 
. Looking at the factors of , which is 
, we try to split the numbers in a way that gives us the correct sum and product. Trying 3, -2, and -8, we see that they add up to 
and multiply to 
, so they work. That means the roots of the polynomial are -3, -2, and -8, and the factorization is 
. Multiplying it out, we get 
, so we find that a = 46.
be an acute, scalene triangle, and let 
, 
, and 
be the midpoints of 
, 
, and 
, respectively. Let the perpendicular bisectors of and 
intersect ray 
in points 
and 
respectively, and let lines 
and 
intersect in point 
, inside of triangle . Prove that points 
, , , and all lie on one circle.
denote the set of positive integers. Find all functions 
such that for positive integers and 
![\[f(a^2 + b^2) = f(a)f(b) \text{ and } f(a^2) = f(a)^2.\]](http://latex.artofproblemsolving.com/c/1/f/c1f8ffe04cfcc45b498f3931a4796d5c56dc04d0.png)
and 
are erected outside an acute triangle 
Suppose that ![\[\angle BC_1C+\angle CA_1A+\angle AB_1B=180^{\circ}.\]](http://latex.artofproblemsolving.com/3/3/7/3378f0c4409d14bc0afddf2616992c13f624be3b.png)
Prove that lines 
and 
are concurrent.
such that the following property holds: if we list the divisors of 
in increasing order as 
, then we have![\[ d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}. \]](http://latex.artofproblemsolving.com/a/d/c/adc94af88b3579164aabba51bd021442133e364a.png)
be a function such that 
for all pairs 
of positive integers. Prove that there exists a positive integer 
which divides all values of 
.
We’ll split into two cases. is unbounded. In that case, let 
be an infinite sequence of integers such that 
for each 
.
take large so that 
. Note that 
and similarly 
. Therefore we have that 
, hence 
. As increases 
gets arbitrarily large, implying 
for all , so 
and 
divides each 
, and we’re done. is bounded by some 
. For any 
and 
, note that 
implies 
because 
. Consider primes that divide infinitely many and let 
be the set of all such primes. Let 
be the smallest positive integer with 
; it follows that for any 
with 
, we have 
, which contradicts the minimality of unless 
. Notice this allows us to associate each prime with an “order” 
such that 
. Suppose for contradiction that 
for each 
. is finite, and if 
, then 
for each and each , so no can divide 
. But the sequence 
is bounded and infinite, so it takes some value greater than one infinitely many times, meaning there is a prime 
which divides infinitely many of the 
. But this would imply 
, contradiction. Therefore it follows that some has 
. But now by definition there are arbitrarily large with , and 
, so this implies for all , and we’re done.
is bounded. to be Soumil if there's infinitely many integers such that 
. For a soumil prime , define it's lavil to be the set 
. Note that if 
then 
, thus (say by Euclidean algorithm), there's an integer 
such that 
. be the set of all soumil primes. Now I claim atleast one of 
where 
will be equal to 
(which would imply the proof). Assume not. Then define 
, and consider the set 
where 
varies over integer. Note that by definition of soumil primes, the union of all lavil sets contains all but finitely many integers. But the elements of 
don't belong to any lavil set, which is a contradiction so done. 
is unbounded.
.) We say the interval ![$[i, j]$](http://latex.artofproblemsolving.com/a/6/4/a644edd67caa59eaded765c417b6d9822f782ec2.png)
is soumil 
for each ![$n \in [i, j]$](http://latex.artofproblemsolving.com/7/a/a/7aa2f478424d03eb80a5eabf9c14e4b5ccc2ba25.png)
. For each positive integer , there're infinitely many soumil intervals of the form ![$[mk, m(k+1)-1]$](http://latex.artofproblemsolving.com/a/5/e/a5ef5035410c44e3f261206bc7de03adfeffb42c.png)
.
, and an integer 
, and a soumil interval ![$[n, 2^M+n]$](http://latex.artofproblemsolving.com/4/a/d/4adda65d455d6a07ea96dfc5d849b05de6afccdf.png)
. Then 
, and thus 
so subtracting them gives 
which gives the conclusion .
. Then 
for all .
. 
for all 
, for some constant 
(otherwise 
is the required constant).
, then 
. In particular, 
if 
.
then 
, so 
. is unbounded: if takes only values in 
then taking any 
primes larger than gives a contradiction. is unbounded. Let 
be a local maximum, meaning 
. We will assume and 
are large enough such that 
, 
. Then: 
However, all the right-hand sides are supposed to not be divisible by 
, yet we assumed 
, contradiction.
and 
then 
. is bounded.
be a prime number. By Dirichlet's theorem, there exists a sequence of prime numbers 
such that
By pigeonhole principle, there exists a increasing sequence 
such that
From 
, we get 
by applying the Claim repeatedly. Therefore, if 
then 
.
is unbounded, we get for every 
which is the desired result. is unbounded. 
iff 
. Since is unbounded, there exist infinitely many number. is , then 
for all 
. Let be a positive integer and be a sufficiently large number. From the condition, we get
Since is sufficiently large, we get 
which implies that is linear.
such that 
for all .
. Had I known that problem existed beforehand I may have not sent my problem to be considered for IMO.
is bounded or not. is unbounded. This means that there is an infinite sequence of \textit{peaks} 
such that 
for all 
. Note that 
and 
, so in fact 
. For any given , we have for large enough that 
, so![\[f(x_n)-f(x)\mid f(1)+f(x_n)-f(x+1),\]](http://latex.artofproblemsolving.com/d/3/4/d342b3f00e0907df77c188ee31692f51d61b9978.png)
so 
for arbitrarily large . We see that 
can be arbitrarily large, so we must have 
, so 
. Thus, 
for all . is bounded. Note that 
, so 
. Thus,![\[\cdots\mid\gcd(f(3),f(1))\mid\gcd(f(2),f(1))\mid\gcd(f(1),f(1)),\]](http://latex.artofproblemsolving.com/c/6/8/c68c55b413860a143ed0eb8385239ee4e43e3f2d.png)
so either 
for large enough , or 
for all , in which case we're done. So WLOG, suppose that 
for all 
.
for 
. To see this, note that![\[f(xy+1)\mid f(x)+f(x(y-1)+1)\implies\gcd(f(xy+1),f(x))\mid\gcd(f(x(y-1)+1),f(x)).\]](http://latex.artofproblemsolving.com/e/9/6/e960c30aa4a9ee26e5a349c2b5270ee0b7c65b7e.png)
Iterating this gives 
, as desired. Thus, any two terms in![\[f(N),f(N+1),f(N(N+1)+1),f(N(N+1)(N(N+1)+1)+1),\ldots\]](http://latex.artofproblemsolving.com/8/d/2/8d245518073427f044592c82a05201504bfad922.png)
are relatively prime, so in particular, any two terms are distinct. But this is an infinite sequence of 
for distinct values of , so is unbounded, which is the desired contradiction.
for all 
. We distinguish two cases:
For all , 
has an odd prime factor
we have
Hence any prime factors of must also be a prime factor of 
where is any positive integer less than . Since 
has only finitely many prime factors, there exists a prime p such that 
for all positive integers . We that 
for all 
.![$[2^k,2^{k+1}]$](http://latex.artofproblemsolving.com/f/9/d/f9d2d35c1bb617f8432036e427849c8935ff6431.png)
has this property, indeed we have 
. Now note that if then since 
together with
we have 
and therefore we complete the inductive step and therefore we're done.
There exists 
such that for all 
we have the fact that is a power of 
.(We assume that is the minimal choice) there exists a number such that for all we have 
is a power of 2.
and , then we have 
therefore 
by Euclidean algorithm. That is
Let be the minimal number such that 
is even. We claim that if 
then is odd. Otherwise, suppose 
, by 
we have 
this contradicts the minimality of 
The sequence 
is unbounded
Suppose 
for all , then since
We have 
hence 
is also bounded, therefore by pigeonhole principle there exists an infinite sequence of numbers 
such that
for all 
.Let this number be 
, then since 
, from we have
, using the same induction method as in Case I we have 
for all positive integer , contradiction.
Let be an integer, denote 
by , then
Suppose 
, and 
, 
, then we prove by induction that 
for all positive integers 
so we're done. In particular, let 
be the order of mod , pick n such that 
for all integer 
, we obtain that 
, and since 
we must have 
that is, is bounded, which violates CLAIM 1.
, then we prove by induction that 
for all positive integers 
so we're done. pick n such that 
for all integer , we obtain that 
, that is, is bounded, which violates CLAIM 1.
If 
, then
either
or
holds,
This violates CLAIM 2 since 
holds, then we let 
. We prove by induction that
for all integer not divisible by 
. Indeed from we have 
From CLAIM 2 we have 
and therefore 
, this completes the inductive step. Now we have, for all integers 
,
that is is bounded, this violates CLAIM 1, so we prove CLAIM 3.
we have
. Note that 
implies that for all integer we have 
,suppose 
, we have
applying the inductive hypothesis we have
This completes the inductive step and we hence have proof CLAIM 4.
for all integer . Let the terms on the left and right side of the first divisibility be and 
, and the terms on the left and right side of the second divisibility be and .
and 
. If 
and 
, we add them up and apply 
to getwhich is what we want to prove.
or 
must hold.
since 
which can't hold for large .
which also can't hold for large . So CLAIM 5 is proved. to be the minimal integer such that 
is a power of , so we obtain a contradiction, which rejects the case 
is even, using the same reasoning as in Case I, we have that for all , is even, so we're done.
Nowhere near as pretty as the first one tho and , then for all 
. So for the sake of contradiction, assume that 
for all 
, where 
is some integer.
where is a constant
, so by induction we have 
, so 
for 
. Because 
, we also have 
. We will also use these two inequalities: 
for 
and 
for the smaller ones. Writing any as a sum of powers of two and using the inequality as many times as needed, we get 
where is constant.
be the smallest value for which . Then we have 
be the smallest value for which 
and 
. Then 
and we have 
, a contradiction.
for infinitely many values of and 
such that 
. Notice that by our assumption we can make 
arbitrarily small and write it as follows: 
for large enough, say for 
. Take 
and obviously 
is arbitrary) .Say the number of primes that divide 
for some is 
. By claim 2, you can notice that all primes larger than are for some , which means 
. Say the largest prime dividing 
is 
. Notice that for 
, 
, the right-hand side is fixed, and from here there are many ways to prove that this is a contradiction. )
for 
, where 
is some integer
for 
. Remember we had the property of 
to be a power of . It is trivial to see that this forces 
and is a power of , meaning divides all 
with , contradiction
.
is bounded., define the set 
. Call a prime strong , if 
is infinite and weak otherwise. Its easy to see that 
, hence 
, for some 
. Suppose that for all strong primes , 
. Then note that since is divisible by only finitely many weak primes, hence this means that the set 
is finite. Consider, 
and look at 
. Obviously its infinite and has 
not divisible by any strong prime, contradiction. . Hence 
for some strong prime , and the conclusion is immediate.
is unbounded. and force "Cauchyness" on some intervals. for all 
to be a peak if 
. Obviously there are infinitely many such peaks due to unboundedness. Its easy to see that due to size issues, 
holds for all 
.
for all . and such that 
is a peak and 
is huge. Spamming the equality 
, we get :
to be huge we're done. 
for which all the values of appeared before . So there is some smaller than such that 
and by euclidean algorithm divides , and by more application of euclidean algorithm (induct down, begin with 
) we get divides every guy in 
and so. we are done since by assumption every value of is included in this sequence.
denote the assertion. First of all, 
yields![\[f(n+1) \mid f(n) + f(1) \implies \gcd(f(n+1), f(1)) \mid \gcd(f(n), f(1))\]](http://latex.artofproblemsolving.com/9/0/b/90b95fae553752a6200a3c8bd5aad3e672c474d5.png)
always. Now, we only need to consider when there exists for which 
for all 
since![\[\gcd(f(n), f(1)) \mid f(n) \mid \gcd(f(n-1), f(1))\]](http://latex.artofproblemsolving.com/c/9/b/c9b1302c0962adefda6af84b27a32ec93f66de9f.png)
so the sequence 
is in fact nonincreasing, and if it never hits , then the lower bound of the sequence divides all 
, and thus divides all 
, at which point we would be done.
are relatively prime for all sufficiently large , then is unbounded. First, note that 
yields 
hence 
which is analogous to the Euclidean Algorithm, and performing this continuously yields 
. Thus, for pairs 
that are relatively prime, and 
, it follows that 
but since![\[\gcd(f(m), f(1)) = \gcd(f(n), f(1)) = 1\]](http://latex.artofproblemsolving.com/b/c/f/bcf8af678774999b4717d4faa636c11701f140ec.png)
we know 
. It easily follows that is then unbounded; if it were upper bounded by 
, then just pick some 
numbers 
for which their values are all pairwise relatively prime; no two 
could be the same, hence the range of needs to hit at least numbers, thus could not have been the upper bound, a contradiction. is unbounded. Consider numbers for which 
. There are clearly infinitely many of these , else is upper bounded by the largest 
. Pick arbitrarily large 
for which 
is large, and greater than all for 
. Then for any positive 
, note 
but still must be a whole multiple of , hence 
. Note that since 
,![\[f(K) - f(y-1) \mid f(K) - f(y) + f(1) \implies f(K) - f(y-1) \mid f(y-1) - f(y) + f(1)\]](http://latex.artofproblemsolving.com/d/9/f/d9fbb70ebb24236d21bc12dbf9769be3ed6d1ca6.png)
where clearly 
from picking such that is much larger than every one of 
. Finally, this implies that 
for all integers , hence is linear and then induction easily shows that 
, so indeed 
for all , finishing this case as well. does indeed always divide all .
. I did the bounded case first and then died on the unbounded case for a longg time proving useless stuff like 
before I realised simple stuff does work 
has some prime dividing it since 
. Let be an arbitrary prime dividing some value of . Let denote the set of numbers such that 
. Note that 
as well, by the problem statement. Let 
be the elements of . Now, we must have 
. This is because if 
, then 
, not possible. If 
, then 
and is between 
and 
, not possible. So, we have that is just multiples of . be a prime dividing . If the problem is false, then 
is finite, say with maximal element . Pick a prime 
. Note that 
cannot contain any prime divisor that divides for 
since then we would need 
, not possible since 
and 
is prime. Since this is true for infinitely many , we have that there are infinitely many primes dividing some value of . In particular, is unbounded. is unbounded, then it is linear. Call a number a peak if 
for all 
. So 
but since is greater than both of them, we must have 
for all 
. Since is unbounded, there are infinitely many peaks. Let be one such peak.
. Since we can make sufficiently large, we must have that the RHS is 
, so 
which gives 
and so 
itself divides all values of . Therefore, we are done. 
be a function such that for all pairs of positive integers. Prove that there exists a positive integer which divides all values of .
denote the assertion of the given functional equation. We split the problem into two cases.
is bounded.![\[f(n+1)\mid f(n)+f(1)\]](http://latex.artofproblemsolving.com/9/0/c/90c218afc156d0dfb6e9902ff3dfcb3af0f01df2.png)
we have that ![\[\gcd(f(n+1),f(1))\mid\gcd(f(n)+f(1),f(1))=\gcd(f(n),f(1))\]](http://latex.artofproblemsolving.com/a/6/c/a6c44f180111d2121faae99164789e331081b180.png)
Also, by Pigeon Hole, there exists a prime 
such that 
for infinitely many 
, let the set of such be denoted as 
and let 
be their greatest common divisor. By the Euclidean algorithm, we can show that contains all the multiples of . Now, we choose a subset 
of 
(for some prime 
) so that contains the least element of and all the images of the elements are equal. Let the least element be 
, then note that 
for all 
, because of the divisibility condition we got earlier. Now, if we choose the prime so that it divides 
, then we get that divides 
and 
for some 
. And since the only that divides and 
is 
, divides for all natural numbers as desired. is unbounded. gawaskar, if 
for all 
. Note that there are infinitely many gawaskar numbers and 
for all . Now, let 
be a gawaskar number such that 
is huge. Then, by the problem's condition, ![\[f(x+y+1)\mid f(x+y)+f(1)=f(x)+f(y)+f(1)\]](http://latex.artofproblemsolving.com/b/3/d/b3d5cb4822c350911b454b6e6c71e4dd2cd535d4.png)
and ![\[f(x+y+1)\mid f(x)+f(y+1)\]](http://latex.artofproblemsolving.com/4/3/6/436f61995397c73216f3798c044345e65e70ddbb.png)
implying that ![\[f(x+y+1)\mid f(y+1)-f(y)-f(1)\]](http://latex.artofproblemsolving.com/7/d/5/7d56445d0bd95b46cf3ac138c9b01e8d62b45f4c.png)
Implying that 
. Since there are infinitely many gawaskar numbers, we have that 
for all 
. This implies that 
, and since 
, we are done.
divides , then first there's 
values of f divisible by p, then everything afterwards isn't divisible by p. Thus, there exists some s.t. for all 
you have 
.
, then let the first time that appears in be 
. Then, 
. Combining these two results, for 
, 
is relatively prime to all previous numbers. is bounded, you find a contradiction because you can't keep generating relatively prime numbers (finite number of prime divisors). is bounded then we claim that is linear (and therefore of the form 
. There must be arbitrarily long chains of 
, otherwise if all chains were of length 
, then the value would go up by 
and then get halved, which cannot become unbounded. Thus, there exists a chain with arbitrarily large of the form ![$[b-k,b]$](http://latex.artofproblemsolving.com/7/0/0/700d8c07744a850ed4dc28e391b57b8cb2d89f0b.png)
. Next, 
so 
and we're done. .
so we can induct to 
. is alive if for any positive integer , there exists 
such that 
. We say a prime is dead otherwise.
we have 
for some , so is dead by induction because 
since 
. dies on a day if for any we have 
and such is minimal. By definition, every prime has a death day.
so for an odd prime if 
then 
. Therefore no new primes appear in the sequence 
and eventually after all primes that divide die, 
is a power of for all 
for some , and none of them are equal to . This implies is alive, so 
. Therefore since 
we know 
. A corollary is that 
for all 
.
we have 
then by induction 
for all integers 
. So for all 
we have 
, which is a finite positive integer. we have 
be the day when all primes that divide die.
where 
are primes and 
for some constant then 
for all 
.
. Then assume 
for some , so pick the minimal such which must be greater than . Clearly 
so let 
be reduced modulo . Then 
, and by induction on 
using 
, we prove 
which is a contradiction, so we are done. and for arbitrary has an injective mapping to the set of primes at most 
. So 
for constant 
. This is clearly false by the Prime Number Theorem, giving contradiction. doesn't exist, so 
for all , implying 
for all .
. Clearly by summing over the binary representation again, 
for all . By taking the smallest power of 2 greater than , 
, we know that 
so 
since 
.
we must have 
but if 
then 
, which is a contradiction. So 
. So letting 
and inducting on positive integers gives us that 
for 
. However this means if is any prime that divides , then 
for arbitrarily large . This means is alive, so by contradiction we are done.
is bounded and unbounded.
for 
, then 
. Call an integer with 
-cool. I claim that if there exist -cool integers, then they are all consecutive multiples of some positive integer , and is one of them (i.e. they are 
or 
for some 
). I claim that setting equal to the least -cool integer works, which is by induction. Suppose that the smallest -cool integers are 
, and the 
-th smallest -cool integer exists. Then if is this -th smallest -cool integer, 
must be -cool as well, and also must be in as it's smaller than , hence 
, completing the induction. is bounded, so there exists some maximal such that there are infinitely many with 
, and call such fat. The key idea is that for any fat , we have 
for all 
with 
sufficiently large (so 
), where we only achieve 
if and are fat as well. be the least integer such that 
(which exists, since it's at most the smallest fat number). Then if is fat and 
is large, 
. On the other hand, if some 
exists such that 
, then 
: impossible by definition, as 
. This is enough to imply that the gap between large enough consecutive fat numbers is constant (and equal to )., such that 
are large enough, and is fat, so 
is fat as well. Then 
. By fixing and letting vary, this means that is eventually periodic (with minimal period ). large and let 
, which is constant for large enough . Then by our "general fact", divides 
, which implies that it divides 
. Then because there are infinitely many -cool integers, and is one of them, every positive integer is -cool, completing the proof. is unbounded. Let be the minimum value attained by , and call an such that skinny. Further, let be powerful if 
, and overpowered if the inequality is strict, so there are infinitely many overpowered (and thus powerful) . It's easy to see that for all overpowered , we have 
for all , and if is powerful (but not overpowered) this equality holds so long as both and aren't powerful either, and if one is, then both are. with 
and 
. Then we have 
for 
. On the other hand, by our general claim, the set of such that 
is equal to consecutive multiples of some positive integer , including —in particular, the least with 
is (important!). On the other hand, if 
, then 
, so any such must have 
. Hence for , 
where ranges from to some arbitrary positive integer (possibly as well). This means that the skinny integers less than are evenly spaced out with a gap of as well. But since must equal the least satisfying (which is overpowered), we can repeat this argument with a different (larger) choice of overpowered , giving us a different value of , unless 
always (in which case the gap isn't defined). This means that there is exactly one skinny number , which in turn readily implies that if 
is overpowered, then 
is overpowered as well, and they are consecutive (i.e. there is no overpowered number between them). Thus there exists some 
such that the overpowered integers which are at least are precisely those of the form 
for 
. Note that if 
, then 
., pick some such that 
, so 
. We then also have
so 
for all . and consider the equation 
for all 
. Then,
Since 
is unbounded, 
, hence satisfies Cauchy and is linear. This clearly implies that divides all values of , so we're done. 
is unbounded. We have a sequence 
where 
for all positive integers 
. First, by size stuff, we see that 
for every positive integer 
. Likewise 
. So, 
divides 
. Thus, divides 
. But gets arbitrarily large. So, 
. Thus, 
is bounded. First, we claim that there exist positive integers , , and where 
and divides 
and 
. This follows from the fact that is bounded. If there are primes dividing elements in then just consider a set of 
pairwise relatively prime positive integers, by PHP we get what we want. Now, let 
be the set of positive integers where is divisible by . We claim 
for some positive integer . Indeed, if 
are positive integers then 
divides 
. Since divides and 
, it must follow that divides 
. So, 
. Now, we will proceed by induction. Suppose 
for every positive integer 
, we will show . Assume 
. Then, 
. But this contradicts minimality since 
. Now, assume 
. Then 
. But because 
, this implies there is an element in between two consecutive elements. Contradiction. where divides and . But, this implies that 
and 
for some and . So, 
. Implying that divides for all positive integers .
such that for 
, 
. is unbounded.
for all , and inductively we have ![\[ \gcd(f(1), f(a)) \mid \gcd(f(1), f(b)) \]](http://latex.artofproblemsolving.com/c/0/7/c072c57d40ffb2f024ff016ef80e8d69a7a56d3b.png)
whenever . Furthermore, for such 
, it follows by the Euclidean algorithm that ![\[\gcd(f(a), f(b)) \mid \gcd(f(a-b), f(b)), \]](http://latex.artofproblemsolving.com/0/6/7/067c1d599f1b80992a0a8274ee0d495a087d0fe3.png)
and we can accordingly condense this to ![\[ \gcd(f(a), f(b)) \mid \gcd(f(1), f(n)) \mid f(1) \]](http://latex.artofproblemsolving.com/0/3/1/0311602957ed8a8726599c3f08bbde5cf9d968c1.png)
for some . By our assumption, when both and are larger than , 
, which forces 
, implying that is unbounded. 
is Skywalker if and only if 
for each ; clearly there is an infinitude of such numbers. By definition 
for all 
whenever is Skywalker. Let be an arbitrarily large Skywalker, and be arbitrary. Fixing and variating , the original functional equation implies ![\[ f(n-m+1) \mid f(n-m)+f(1), \]](http://latex.artofproblemsolving.com/5/3/d/53dae70fac1ea385db70a0d417636788522c4ec9.png)
which we easily reduce to ![\[ f(n) - f(m) \mid f(m)-f(m-1)-f(1), \]](http://latex.artofproblemsolving.com/b/3/5/b35b4e6ba9accbaab686ff179bdf5d5853d25f4c.png)
so by size reasons we have 
, which rewrites as 
. Inductively we have 
for all 
, but this is a contradiction to our initial assumption that for sufficiently large . We conclude. 
is unbounded by following the Euclidean algorithm, and observing their infinitude, and (where is a large Skywalker) and variating .
(we take the smallest) that does not share the common gcd of the numbers smaller than it; let the earlier common gcd be g. Let 
. Note that 
and by assumption 
. We also extract 
by iterating. By assumption, this is one (otherwise 
); in particular, f is unbounded.
); namely 
for infinite n. Fix and vary n with this property; we have 
which for sufficiently large f(n) s.t. LHS>RHS, we must have RHS=0; in particular, 
, contradiction since f(1)>1 and f(1) is a common gcd, so our inital FTSOC was wrong.
. infinitely many times, then prove one of them divides all by contradiction argument.
is the minimum value attained by . In particular, we prove that divides all values of . Assume the contrary. Then, obviously is nonconstant. Notice that 
implies 
since 
. Consequently doesn't divide for all sufficiently large values of .
satisfies 
. Then, the condition implies that 
. Since equality holds only if 
, this tells us that either 
or 
. Consider the smallest positive integer such that 
. Suppose that a positive integer satisfies 
. Then, the condition implies that 
and hence 
which is a constant number. satisfies 
. Then, we have 
. It is clear that these observations are enough to conclude that is bounded. (Actually, this implies that if is unbounded we must have 
.)
be the largest value that appears infinitely many times in . Let 
be the numbers mapped to by . Consider two sufficiently large positive integers 
such that 
is also very large. Then, we have 
and hence 
. The condition implies that 
. Since is very large, we have 
. Hence, 
, a contradiction. (We actually dont use the fact that is the minimum here.) be the smallest positive integer such that 
for all 
. Consider the function 
such that 
. Observe that 
for all 
and 
for all . It follows that 
for all positive integers .
is bounded. is bounded. Assume the contrary. Then there exists a positive integer such that the sequence 
is unbounded. Let 
be a sufficiently large term of this sequence. Our condition implies that 
which is bounded by a constant number, a contradiction. . is unbounded.
. We claim that 
. Using the same logic as Case 1, we see that the sequences are unbounded for all positive integers . Consider positive integers such that 
for all 
. Suppose that 
. Consider the largest positive integer 
such that 
. It is clear that 
The condition implies that 
. Hence, 
a contradiction. Then, 
implies that 
.
. Let 
and 
. Then, 
and hence 
for all positive integers and 
. This implies 
. Hence, 
. 
then 
use euclidian division algorithim to prove the claim . is bounded above or in other words attains finite values.
be the largest value in its range which repeats infinitely often. say is the smallest natural number such that 
.
for large is large we have 
if 
we know 
using this the claim is easy to see . , 
or 
where 
is large covering all large solutions for not divisible by pick some large such that 
we know then 
divides 
.
such that 
and choose some large 
such that 
to similarly get 
and repeat similarly as a sum of its divisors only way to do is 
, smaller 's automatically follow pretty easily . is unbounded .
largest odd factor of any natural no , observe 
always .
where is a odd no. By induction.
eventually turns into powers of 2 .
is the smallest power of in the sequence . come in the sequence 
and do 
, its easy prove that the sequence wont be bounded . which will give u this claim .
where is odd has to be odd[can be proved with more that if it wasent the case all terms would be even]. , we know there exist ifninitely many such that 
is a power of , by which the result isnt hard to see[ too lazy to add the details ]
is bounded. If we assume that is unbounded we can say that there are infinite amount of that 
is the prefix max. So it becomes that for any 
. Now if we take large N and some x to be 
and it becomes that 
which in turn means that
so 
. is bounded we can assume that there is a set of values of lets call that they appear infinitely many times in . It is clear that the 
divides all less than . we can easily see that the 
. So it means that every occurrence of a element of is divisible by some "primitive occurrence". we will get that that element of is divisible by in turn all of will be divisible. So every "primitive" occurrence divides every occurrence of elements of . Every if is large will be an element of which means that every will be divisible by some "primitive" occurrence but we can take an that isn't divisible by any so thus a contradiction.
is bounded, say by . Then there exists a nonempty set of positive integers such that for any 
, 
for infinitely many values of . Otherwise, every only divides 
values of , and we can only define for less than 
values of .
, let 
be minimal such that 
, and let be the minimum among the . Furthermore, let 
be the values with this 
in increasing order.
, 
.
so we inductively have 
. If 
, this is less than , hence we must have 
.
has infinitely many terms, so for any , we can find a 
, and the above process implies 
, as needed. 
. of divides only finitely many . In particular, for sufficiently large primes , 
implies 
. But this contradicts bounded. is unbounded. Then by definition, there exists a sequence 
such that 
for all 
. For these 
, we must have 
as 
for all . In particular, we have the following claim:
for some constant .
for each . Take some 
; by the previous property, ![\[f(k) + f(n_i-k) = f(n_i) = f(k+1) + f(n_i-k-1) \implies f(k+1) - f(k) = f(n_i-k) - f(n_i-k-1).\]](http://latex.artofproblemsolving.com/9/c/f/9cf44904f508073a3667494a13bdb198658f497a.png)
Let 
and 
. We have![\[f(n_i-1) \mid \gcd(f(k-1) + f(n_1 - k), f(k) + f(n_1-k-1)) = \gcd(f(k-1)+f(n_1-k), a_{k-1}-a_k).\]](http://latex.artofproblemsolving.com/d/5/2/d5264888a51d146a22c34b7deb851188b14b307c.png)
In particular, 
. But 
is unbounded, hence 
is unbounded, so 
, as needed. is linear in . Let 
and 
; if and are relatively prime, then 
, which is a clear contradiction as 
. Hence and share a common factor , and this divides for every .
for some fixed we get the result. be the largest value such that for all we have that . Clearly from the definition we can find values such that for any 
we get that 
, now take a value of such that 
. I claim that we have for that value of that 
. Suppose that 
, we must have that 
if 
we have that 
, thus 
however this is a contradiction. Thus for all we have that . Now suppose that for some 
that 
. Clearly we have that 
and thus for all 
we get 
. Thus we must have unless the result holds true that is coprime to . Now let be a prime such that . Clearly there exists infinetly many such that 
. Thus we can choose abitrarily large such that 
. Now consider 
as , we get that 
as we can make abitrarily large, as we can get that 
for all sufficiently large this suffices as this means that for all . still exists. Clearly we must have that if 
that 
. Thus if we let the first primes be 
, 
, 
, 
. We know that for all we have 
. Now let be a value such that 
. We get that above some point from that we must have for all 
that 
. Let the largest prime divisor amongst 
, 
, , 
, such that 
be . Suppose is the th prime, now let be a value such that 
. Take the first primes. Clearly a prime divisor of size at least 
divides one of 
which contradicts the size condition thus implying the result.
.
Where 
,
.
,
,![$n \in [mk, m(k+1)-1]$](http://latex.artofproblemsolving.com/6/6/f/66fa942ebb159bf44b9db83a3227899b15cc4aa5.png)
with 
.
with ![\[ g(n+k)g(n+k-1) \cdots g(n+1) > 1 \]](http://latex.artofproblemsolving.com/d/9/6/d96b42cb0ade28ecfe7f40a77082126859432839.png)
so ![\[ g(n+k)g(n+k-1) \cdots g(n+1) \geq 2 \]](http://latex.artofproblemsolving.com/9/f/d/9fdc27558376d5ecd6ffb2828983edb8e617ac76.png)
, using this implies 
.
.
for all ![\[ f(n) < 2\max(f(1), \cdots, f(mk))+ f(1)2k \]](http://latex.artofproblemsolving.com/9/a/8/9a84bc0ce953dca4feb729e25927b30495c80f74.png)
, a contradiction !
.
,
,
,
be the smallest number such that 
is not divisible by 
(assume for contradiction that these all exist).
,![\[p \nmid f(m) + f(x) \implies p \nmid f(m + x).\]](http://latex.artofproblemsolving.com/d/9/1/d910ac4c931ebb208363a235516e85679c0a70ff.png)
Repeatedly applying this means that 
for all sufficiently large 
.
which is greater than 
must be divisible by some prime in 
satisfying ![\[q_2 \equiv \ell_1 \pmod{q_1}.\]](http://latex.artofproblemsolving.com/e/b/d/ebd1b8429d2f754db3be4028c3ee7115768d4ae0.png)
(This is true by Dirichlet's Theorem, since 
so 
.
can't be divisible by 
and 
,
and is greater than 
,
,
satisfying ![\[q_3 \equiv \ell_1 \pmod{q_1}, \quad q_3 \equiv \ell_2 \pmod{q_2}.\]](http://latex.artofproblemsolving.com/c/6/7/c6789f0e699704d1fe4e8fd4d4471fda143804be.png)
(This is again true by CRT and Dirichlet's Theorem, since 
as 
,
are prime.)
can't be divisible by 
.
satisfying ![\[q_4 \equiv \ell_1 \pmod{q_1}, \quad q_3 \equiv \ell_2 \pmod{p_2}, \quad q_3 \equiv \ell_3 \pmod{p_3}.\]](http://latex.artofproblemsolving.com/c/6/d/c6d5564c3f8e06a9333de601025e725125b9e066.png)
Then 
can't be divisible by 
,
.
for which 
can't be divisible by any of 
for some constant 
for some 
and 
,
.![\[f(t + k) \mid \gcd(f(t) + f(k), f(t - 1) + f(k + 1)).\]](http://latex.artofproblemsolving.com/5/d/7/5d7e79a6e26c72a47a6ff0beabdff7c42d0309ae.png)
However, the second term must be strictly smaller than the first, so this can't be 
,![\[f(t + k) \leq \frac{f(t) + f(k)}{2} < f(t),\]](http://latex.artofproblemsolving.com/1/9/4/194abbc6a4044380f6fb0f1fd4d8573bc065d8d7.png)
since 
,
,
,
.
,
.
with 
then 
,
such that 
,
for some 
,
.
,
which allows us to conclude using the fact that 
There are infinitely many 
such that 
for all 
,
means that 
Then, taking the minimal 
such that 
,
must be in an arithmetic progression because unless 
for some 
,
and as at each step we can increase by at most 
which is a contadiction to the choice of 
.
,
,
such that 
.
meaning that for each 
,
such that 
.
which is a contradiction as, due to the condition that 
,
as to ensure that 
which is a contradiction. 
,
be the set of integers 
.
.
for all 
such that 
or 
with 
for all 
form an arithmetic progression with 
for 
,
so 
for some 
we have 
,
,
,
due to claim 1. This gives 
,
.
be the minimal element in 
for all 
.
for all 
.
for all 
for any 
for all 
,
for 
.
we have 
for 
.
such that infinitely many 
.
,
.
for all 
so 
for all 
grows arbitrarily large for large 
.
is an arithmetic progression with 
because 
,
,
exists, and is either 
hence 
)
.
afterwards, and (as many have pointed above) if the conclusion is false, the case 
for all 
)
divides 
.
.
.
from primes 
and 
,
for 
with any positive constant 
,
is bounded (here 
number of primes 
)
such that 
for all 
for all 
.
,
for any 
by induction and we are done in this case.
be the prime divisors of the values of 
be those of them that divide infinitely many values of 
,
such that 
for all 
,
,
should have appeared before 
,
be the minimal positive integer such that 
;
.
(otherwise 
,
for all 
,
has prime factors only among 
.