AoPS Academy
, we define a sequence by 
, 
, and 
for 
. Prove that if 
for some 
, then the sequence is periodic.
contains only one set of three distinct points, 
and 
which are the vertices of an equilateral triangle.
be the set of all triples 
of positive integers for which there exist triangles with side lengths 
Express ![\[\sum_{(a,b,c)\in T}\frac{2^a}{3^b5^c}\]](http://latex.artofproblemsolving.com/9/f/6/9f6e0cee87e5b6958e143ff23b887bcd876f6cba.png)
as a rational number in lowest terms.
is a finite set, let denote the number of elements in . Call an ordered pair 
of subsets of 
if 
for each 
, and 
for each 
. How many admissible ordered pairs of subsets 
are there? Prove your answer.
where 
, 
, and 
are nonnegative integers.
. Note that 
, 
, 
, and 
. Thus 
there exist nonnegative integers ,, and such that 
. Note that 
implies 
but then if 
is congruent to 
modulo 
it must be congruent to modulo 
as well as we inspect on the 
cases where the set of residues for , , and is 
,
,
, or 
.
with 
. Let 
. These constructions suffice:
Clearly 
is a nonnegative integer (AM-GM, 
is a ring). So it suffices to show that 
is impossible.
. If 
then 
, so 
. So 
. Then 
is divisible by , so 
. But then .
. We claim can take on any nonnegative value that isn't 
or 
. Note that plugging in 
gives 
, plugging in 
gives 
, plugging in 
gives 
, and plugging in 
gives . is divisible by , then it is also divisible by . This is true because we can factor as![\[T=(A+B+C)((A+B+C)^2-3(AB+BC+CA)).\]](http://latex.artofproblemsolving.com/e/a/3/ea375bca4fa257115092cf95765c5600547fcf5a.png)
It is evident that if divides one of the factors, it must divide the other, so 
, as desired. This completes the solution.
![$f(x) \in \mathbb{Q}[x]$](http://latex.artofproblemsolving.com/e/d/a/eda31c06f8b59911d0cedd1128bbd5499094fc2c.png)
and 
is an element of ![$R := \mathbb{Q}[x]/(f(x))$](http://latex.artofproblemsolving.com/4/9/d/49d336ecc1bf5fe0cc84202407461abf69c1b5ff.png)
, then the Norm of is: taken over all 
roots of 
-linear map 
given by multiplication by .
is the Norm of 
when we take 
. Since has two factors over and three factors over 
, the same will also be true for . The fact that ![$\mathbb{N}[x]/(x^3-1)$](http://latex.artofproblemsolving.com/e/f/4/ef492e47d0fdfd9a66b9ddf7b160a90d395d432d.png)
is closed under multiplication implies that its set of Norms (the set of values in question A1) is also closed under multiplication. This may be a good way to construct similar exercises.
![\[a^3+b^3+c^3-3abc=\frac 12\cdot (a+b+c)\sum_{\mbox{cyc}}(a-b)^2.\]](http://latex.artofproblemsolving.com/9/8/c/98cdc7d9bb55c6ed37113ec2fc45ac992d8e279c.png)
So by taking 
we can achieve any 
and by taking 
we can achieve any 
. It remains to figure out which multiples of we can achieve. We can achieve multiples of by setting 
to get 
.. Then exactly one of 
and 
is a multiple of . If the latter is the case: if some two of 
are the same mod , then all are, but this cannot occur so are all distinct modulo . This is also a contradiction. So then the first case holds. Then are all congruent modulo or all distinct modulo which again ends up causing a contradiction. and multiples of are achievable.
and Introduction to Number Theory level Modular Arithmetic? If so, can someone provide a basic solution like that? Just wondering.
as residues 
such that everything else works?
residues. is a multiple of . We claim that 
and 
, which together imply that 
.
by FLT, so .
and permutations then . These are the only possibilities since . can only be 
. We can show that all of these are achievable:
, is possible.
, 
(except for ) is possible.
, 
is possible.
, 
is possible.
, 
is possible.
, 
is possible.
, 
is possible.
, 
is possible.
.
..
in , and then show 
.
(indeed, this covers 
mod ).
works.
(indeed, this covers 
mod ).
works.
, set 
. This works. For 
, set 
.
or 
.![\[f(A,B,C)=(A+B+C)(A^2+B^2+C^2-AB-BC-AC)=(A+B+C)((A+B+C)^2-3(AB+BC+AC))\]](http://latex.artofproblemsolving.com/c/7/d/c7d7c28b8d40b487a1ccd24d5bed182a19e99cb1.png)
must divide and 
. If divides 
, then divides , a contradiction. If 
, then , a contradiction.
.![\[f(A,B,C)=(A+B+C)(A^2+B^2+C^2-AB-BC-AC)\]](http://latex.artofproblemsolving.com/3/d/5/3d5cec918d9d55efa51b68e1fca0cde90998a0cd.png)
, because 
.
.
, which implies is nonnegative. 
that are either 
or 
mod 3 or mod 9.
, then 
is a construction
, then 
is a construction
, then 
is a construction is divisible by , it must be divisible by . This can be seen by factoring and looking over all residue combinations of 
módulo that allow the expression to be divisible by . Thus, these are all the cases.
with 
.
, we get .
, we get 
. Similarly, by taking 
, we get 
.
, we get 
. 
and 
.
to get the result. 
. while . Finally, . We now show that it is impossible for 
.
and 
is possible only if:
,
.
, then 
and 
which means 
. Hence, 
.
.
then 
. If 
then 
, while 
. Hence, . then , as claimed.
work for every 
.
work. Let's see the constructs for these values:
(constitutes for 
) for all non negative integers .
(constitutes for 
) for all positive integers .
(constitutes for 
) for all non negative integers .
Thus 
are not achievable. 
works.
First we prove if 
then 
, notice 
, now 
, now that forces 
, now that implies 
for some 
and hence 
, so clearly 
are not possible. 
gives 
under , which gives as residues under .
we get 
which gives residues under , and finally for 
we get , which finally accounts all possible values of for non negative integers . 
is a multiple of 3, denote 
must be a multiple of .
, denote 
, where the integers in the parenthesis are the remainders of divided by . Test three cases, 
, 
yielding 
as desired.
gives 
,
gives 
, and
gives 
. Letting 
vary gives all solutions.
, 
follows by inspection.
Thus, we can obtain all integers 
such that 
.
Thus, we cannot obtain numbers that are or 
, and we are done.
or 
mod . Indeed, by setting 
we get 
which covers all multiples of , and by setting 
we get 
which covers all non-multiples of . or mod integers fail. This just stems from the observation that![\[a^2+b^2+c^2-ab-bc-ca = (a+b+c)^2 - 3(ab+bc+ca) \equiv (a+b+c)^2 \pmod 3\]](http://latex.artofproblemsolving.com/8/1/0/8104b784cf4fd2f5fd7f86d0e8ce0826200ccb74.png)
so either 
is the product of two multiples of or two numbers relatively prime to .
and 
are achievable, we will show that 
,
implies 
.
iff 
,
iff 
,
iff 
.
,
,
,
are 0, -1, 1 
(in some order). Using the above observation, it can be checked that cases i) and ii) imply 
.
equivalent to 
.
.
gives 
and 
gives 
,
gives 
.
work. To construct you just take 
,
,
.
.
