AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
and 
such that
be a real number. Determine all natural numbers 
for which there exist distinct natural numbers 
, 
, 
, such that
denotes the greatest common divisor of natural numbers 
and 
).
with 
, point 
lies on the circumcircle of such that 
. The line through parallel to 
intersects 
in 
and 
in 
. Prove that the center of the circumcircle of triangle 
lies on the circumcircle of triangle 
.
, no two of which are 
. Prove that:
points and some chords between them is given.
In every step we can take two chords 
with a common point other than 
and erase exactly one of and draw 
let 
be the minimum of chords after some steps. Find the maximum of over all initial positions.
In every step we can take two chords with a common point other than and erase both of and draw let be the minimum of chords after some steps. Find the maximum of over all initial positions.
be a positive integer and let 
and 
be positive integers congruent to 1 modulo 4. Prove that there exists a positive integer 
such that at least one of the numbers 
and 
is divisible by 
be the lengths of the sides of a triangle. Prove that![\[\frac{1}{(a-4b)^2}+\frac{1}{(b-4c)^2}+\frac{1}{(c-4a)^2} \geqslant \frac{1}{ab+bc+ca}.\]](http://latex.artofproblemsolving.com/7/4/b/74b7aa5621bc52977d9acd448d74293dc27a8e00.png)
and be arbitrary points on the sides 
and 
of triangle , respectively. The circumcircle of 
meets for the second time the circumcircle of 
at point . Line 
meets line 
at point , while line 
meets line 
at point 
. Prove that lines 
and 
pass through the same point.
with circumcenter 
. 
and 
intersect the altitude from 
to at points 
and 
respectively. 
is the circumcenter of triangle 
and 
is the reflection of over . 
is the second intersection of circumcircles of triangles 
and 
. Show that 
are collinear.
and 
Find the value of 
and such that 
and 
is a prime number
, 
, 
, 
, 
, 
be positive integers and let 
.
divides 
and 
. Prove that is composite.
are multiples of 
. Evaluating 
at 
we get that 
is a multiple of . is composite, since 
are all strictly less than .
is prime.
is a solution then 
is also a solution. Note that does not change. Denote 
. We can claim that 
also satisfies the conditions.
. But this is impossible, since 
are all 
. 
now so we get 
, suppose is prime then it must be less than one of but as 
so absurd and done.
be prime. Note divides 
. Substitute 
we get divides 
and
, 
and 
. However, each of 
are smaller than , a contradiction.
be a fixed prime. We say a 
-tuple 
of integers is good if 
and 
and 
. is good then so is 
.
-tuple of positive integers. If not, WLOG is the smallest of the six numbers. Then by repeating the claim, the tuple 
is good. But now 
and 
, contradiction.
Now, assuming that is prime, we see that![\[(X-a)(X-b)(X-c)=(X+d)(X+e)(X+f)\]](http://latex.artofproblemsolving.com/f/a/5/fa55af7a46e2a02d5006a87b46caa4c436e0c0bf.png)
over ![$\mathbb{F}_S[X]$](http://latex.artofproblemsolving.com/1/4/a/14a21d85873231e62118fb1bef37dbdd0d4c09b5.png)
, so because of unique factorization, we have WLOG that 
, 
, and 
. In particular, this means that 
. However, 
, so this isn't possible. Therefore, couldn't have been prime to start with. 
, so assume for the sake of contradiction that is prime. Let 
and 
. Multiplying out, we get that 
for all integers . In particular, we get that for an integer , divides 
if and only if divides 
, which, because is assumed to be a prime, means that 
is just some permutation of 
modulo . WLOG, assume that 
, 
and 
modulo . But this means that 
, 
and 
are all multiples of , which is impossible, because they are positive integers which sum up to .
is prime. Notice that 
for all 
.
to be 
we have that 
in 
using that is prime, yet, adding any such values of 
, we have that 
which is a contradiction. 
is divisible by for all integers . Thus,![\[S\mid f(a) = -(a+d)(a+e)(a+f)\]](http://latex.artofproblemsolving.com/8/e/1/8e154252998ba701b0a59a63e0b705d60e79d7a5.png)
To finish, cannot be prime because 
, so we're done. .
is prime, and take polynomials 
and 
Note that ![\[P(x)\equiv x^3 - (a+b+c)x^2 + (ab+bc+ca)x-abc \pmod S\]](http://latex.artofproblemsolving.com/7/f/5/7f59df6e2f3974a5e80bd5b4ac3dd868230000a4.png)
Note that on the other hand, ![\[Q(x)\equiv x^3 + (d+e+f)x^2 + (de+ef+fd)x+def \pmod S\]](http://latex.artofproblemsolving.com/8/4/2/84230bcf983b2168ded438594f9521775add2c1a.png)
Now, 
Note that this is divisible by 
In particular, 
is divisible by Note that each of those factors are less than but is prime, which is a contradiction.
This means that 
for all 
as the resulting polynomials are equivalent under modulo . Letting 
, 
but 
, and thus must be composite.
is prime . Then we have the following equations.
We will construct numbers 
such that:
In fact, this is not so hard to do. It is just enough to take 
and 
. It is easy to see that they satisfy the first congruence. Note that:
We see that the second desired congruence is also satisfied by given congruences. Also, observe that:
We see that the third desired congruence is also satisfied by given congruences.
are positive integers and their sum it , then they all are less than . WLOG is the largest among . With each construction we increase by 
and decrease 
by . We can keep doing it until becomes . Suppose that we needed for that constructions, in other words 
. Consider congruence:
We see that it implies that 
. WLOG assume that 
is the one which is divisible by . Then 
, which is contradiction, since it forces 
to be . composite as desired.
is prime. We will make use of these handy identities in the solution.
The following claim is the crux of the problem.
for all 
.
. For ease of notation label 
, 
and so on. Now finally for the inductive step, we will just work backward.
By the induction hypothesis, we will cancel of 
term. It is not hard to see that 
as well.
It isn't hard to expand this out and realize its a tautology. So, the induction is complete.
. This would give![\[S = a + b + c + d + e + f \mid (a + d)(b + d)(c+d).\]](http://latex.artofproblemsolving.com/3/2/d/32db74e588d686d5a1aa6a1709ed3b9955024515.png)
Since is a prime, it must divide one of the factors. But since all the factors are positive and less than , its the desired contradiction. 
as value of .
is a prime.
, 
and 
. Summing these up gives, 
Also, 
. is a solution then, 
is also a solution with 
.. WLOG that be .
. But therefore must divide one of which isn't possible as, 
. This gives a contradiction. 
was prime. Then the polynomials 
and 
have equivalent expansions modulo , hence we must have 
. But then 
: contradiction. 
hence as 
. Now , 
assume is prime, then as we have we have at least one of 
but since 
this is absurd for 
, hence our assumption false and hence is composite .
![\[
(t-a)(t-b)(t-c) \equiv (t+d)(t+e)(t+f) \pmod{S}
\]](http://latex.artofproblemsolving.com/8/8/6/8869db968e5197f8922c1fbf869591364313b8bb.png)
for all integer 
. Suppose for the sake of contradiction that was prime. Take 
. Then, divides one of , 
, 
. However, since are positive integers, that would mean that one of 
is equal to . This is a contradiction as the rest of the variables could not be positive, so must be composite.
be a prime
in 
we're done.
be an integer. Note that divides the quantity 
Now there are cases. is one of 
WLOG suppose it is 
Letting 
gives 
so switching the positive sign yields 
If was prime, then it would have to divide at least one of these factors, say 
(the other cases are symmetrical to this). Then 
which is a contradiction due to size issues. is one of 
WLOG suppose it is 
Letting 
gives 
and repeat the size argument from the previous case. must be composite, as desired.
for some prime 
Then we get a vieta-like relation modulo 
This implies that and 
are roots to the same polynomial with coefficients modulo 
are multiples of 
for some integer 
which violates the condition that 
or is prime. Therefore must be composite.
which satisfy the given conditions. We call such a pair a good pair and if 
then we say that it is a 
good pair. We start off by proving the following nice result about good pairs. for which there exists a good pair , the pairs 
and 
are also good.good if they are good at all, since the sum 
does not change in either instance. We show that if is good then the pair must also be good. This is a mere calculation. Note that,![\[ (a-1)(b-1)(c-1)+(d+1)(e+1)(f+1) = (abc+def) -(ab+bc+ca-de-ef-fd) + (a+b+c+d+e+f)\]](http://latex.artofproblemsolving.com/7/9/d/79d92d2b07649a2309675c9bbd40793110c64920.png)
where each of the bracketed terms are known to be multiples of . The proof of the other is entirely similar, so this finishes the proof of the claim.
good pairs for any prime . By way of contradiction, say there exists such a prime and a good pair . Then, WLOG say the minimum element of the set 
is . By way of our claim, it follows that the pair 
is also good. Note that here, 
, 
and 
are all positive integers. Then,![\[p|(0)(b-a)(c-a)+(d+a)(e+a)(f+a)=d'e'f'\]](http://latex.artofproblemsolving.com/1/4/8/1486fa5dd4ccf8439f3f3f1adb0a7413d458a2b6.png)
Since is a prime, this implies that divides one of 
, 
and 
. But, since 
where the first 3 terms are non-negative and the last two terms are strictly positive,![\[p = (b-a) + (c-a) + (d+a) + (e+a) + (f+a) \ge d'+e'+f' > d',e',f' \]](http://latex.artofproblemsolving.com/f/f/8/ff81a816a7e657c13279ad8009a283d59f17697a.png)
which is a clear contradiction. Thus, there cannot exist such a prime which proves the desired result.
.,
, then 
. However, are all less than , contradiction if is prime.
is prime. Observe that![\[
a + b + c \equiv -d - e - f \pmod{S}
\]](http://latex.artofproblemsolving.com/6/5/b/65b17328dc50401bca6c02b93af26af0764e5fed.png)
![\[
abc \equiv -def \pmod{S}
\]](http://latex.artofproblemsolving.com/a/e/f/aefdb33a5e701a2c2673a276cadafcb2caf88893.png)
![\[
ab + bc + ca \equiv de + ef + fd \pmod{S}
\]](http://latex.artofproblemsolving.com/d/0/c/d0cd03b97a83dca5632a66f383f808bf142b6186.png)
By Vieta, we have that for every positive integer 
, the following relation holds:![\[
(n + a)(n + b)(n + c) \equiv (n - d)(n - e)(n - f) \pmod{S}.
\]](http://latex.artofproblemsolving.com/8/7/5/875c367d3f930c1e5f03cd7ef8c614aa4dcf8ed1.png)
By setting 
, we obtain that divides one of the numbers 
, 
, or 
.
. In particular, we have 
, i.e., 
.![\[
a + d < a + b + c + d + e + f = S.
\]](http://latex.artofproblemsolving.com/8/7/1/871fdf7fedb6beda5cc926f7cd824bb07efd123e.png)
.
we get cannot be prime, qed.
is prime. Then, 
and 
when taken modulo 
Let 
for 
It is clear that 
and 
and 
So, 
are the solutions of some cubic modulo But, by Lagrange's Theorem, this can only have at most 
solutions, so these sets are the same, in some order. So, 
where 
and 
But, then 
so we have a contradiction.
be a fixed prime. We say a -tuple of integers is good if and and . is good then so is .-tuple of positive integers. If not, WLOG is the smallest of the six numbers. Then by repeating the claim, the tuple is good. But now and , contradiction.
are congruent modulo Thus, 
However, 
However, each of the factors are less than 
which finishes.
. We have 
. must divide one of them but all three are less than 
, a contradiction. So, is composite.
![$S|(c+f)[(b+c)(c+a)+(d+e)(c-f)]$](http://latex.artofproblemsolving.com/b/e/8/be8ea894c975ae3a08306af2d92bc70de652e1e4.png)
,
,
and 
are the same polynomial, mod 
.
.
.
and 
,
for all integers 
.
or 
or 
which means one of 
are nonpositive, contradiction.
.
.
,
and consider 
Taking mod 
.
but 
and so we are done.
has all of its coefficients divisible by 
.
,
,
and clearly inputting 
implies 
,
.
,
,
Letting 
we have 
which is absurd if 
in 
contradiction.
.![\[
(x+a)(x+b)(x+c) - (x-d)(x-e)(x-f).
\]](http://latex.artofproblemsolving.com/7/4/6/74644154e284b0dc05bfe757c76adecafde3cbbe.png)
If 
,