AoPS Academy
with 
odd, which satisfy the equation:
and 
are two sequences between 
and 
and they satisfy 
, prove that 
, and determine when does equality hold
, 
, 
, 
, 
, 
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.
and 
Prove that 
![$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 
.
has a root at 
but 
and so we are done.
has all of its coefficients divisible by 
.
,
,
and clearly inputting 
,
.
,
,
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 
,