,
and 
are taken such that the point 
and 
.
and 
,
and 
are taken so that 
and 
.
.
and 
,
.
and 
be intersection points of lines 
and 
with circumcircle 
,
and 
intersection points of lines 
and 
with side 
.
,
with 
such that 
divides 
for all positive integers 
.
such that 
Follows for all reals 
.
denote the set of positive integers. Find all functions 
such that for positive integers 
![\[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)
be an integer. Rowan and Colin play a game on an 
grid of squares, where each square is colored either red or blue. Rowan is allowed to permute the rows of the grid and Colin is allowed to permute the columns. A grid coloring is orderly if: [list] [*]no matter how Rowan permutes the rows of the coloring, Colin can then permute the columns to restore the original grid coloring; and [*]no matter how Colin permutes the columns of the coloring, Rowan can then permute the rows to restore the original grid coloring. [/list] In terms of 
,
so that 
and 
.
so that 
.
.
that satisfy![\[
f(x^2-y)+2yf(x)=f(f(x))+f(y)
\]](http://latex.artofproblemsolving.com/f/b/b/fbb693770cd90d8a144026608074122e54da5802.png)
for all 
.
Y by Com10atorics, Adventure10, Mango247, and 1 other user
Let 
be a fixed integer greater than 1, and let 
. Show that there exist positive integers 
and 
such that the sequence 
defined by ![\[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\]](//latex.artofproblemsolving.com/b/2/6/b26931e97d94c1b445358b3338b9b3918f3f270c.png)
has all of its terms relatively prime to 
.
Proposed by Jaroslaw Wroblewski, Poland
be a fixed integer greater than 1, and let 
. Show that there exist positive integers 
and 
such that the sequence 
defined by ![\[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\]](http://latex.artofproblemsolving.com/b/2/6/b26931e97d94c1b445358b3338b9b3918f3f270c.png)
has all of its terms relatively prime to 
.Proposed by Jaroslaw Wroblewski, Poland
This post has been edited 1 time. Last edited by djmathman, Aug 1, 2015, 2:54 AM
Reason: formatting
Reason: formatting
be the roots of the equation 
(the characteristic equation of the sequence). Since every prime divisor of 
as a quadratic residue, if we fix 
,
,
(where I changed the notations a bit and took 
)
s.t. 
in 
.
,
.
Can you explain me what does "quadratic residue" mean ?
then 
.
being even we can take 
and then
,
.
,
,
,
is co-prime to 
,
and define 
by recursion
,
,
satisfying 
,
for every 
.
.
.
.
has at two solutions 
modulo 
if 
and 
.
or 
the desired lemma follows.
for 
since we know 
is not 2 or 5.
.
and it's relatively prime to 
we substitute 
and 
and simplify we have
.
then 
=> 
=
so contradiction. If 
then 
also contradiction.
and so 
and 
. Now 
and it's never 0 relatively prime to all 
so we can just say
and 
is relatively prime to all 
(where I changed the notations a bit and took 
)
s.t. 
in 
.
,
.
to be an integer 
,
such that 
.
and 
.
;
.
is even, so 
is no integer!
,
.
.
.
.
is the n-th term of the Fibonacci sequence.
the residues of the sequence 
repeats at 
.
.
.
,
.
for each 
.
,
.
,
and 
.
,
as desired.
?
so 
.
then all terms of 
.
.
which is always of the form 
by Cassini's identity, thus any 
note that 
thus for 
and 
.
The crucial lemma is as follows:-
such that 
for any 
.
,
works (since in this case, one finds that 
,
,
such that 
For all such 
be the smallest such index. Since 
,
.
which means that 
dividing 
.
for some 
.
are the smallest indices by definition, so due to periodicity after 
.
with 
.
As 
,
However, this contradicts the well known fact that 
for all 
.
be all distinct prime divisors of 
gives that ![$i \in [s]$](http://latex.artofproblemsolving.com/3/2/c/32c0a1170be0a83a6bf2a27457c57f3debdde395.png)
.
such that ![$$F_n \not \equiv C_iF_{n-1} \pmod{p_i} \quad \forall n \in \mathbb{N} \cup \{0\} \text{ and } i \in [s]$$](http://latex.artofproblemsolving.com/8/6/f/86fe8c52db379a4388176afa09326c361f15e36c.png)
Using CRT, there exists an integer 
satisfying ![$$Z \equiv C_i \pmod{p_i} \quad \forall i \in [s]$$](http://latex.artofproblemsolving.com/2/b/a/2ba690cfc9ea365260f20d68c40be57cb8b4a5ef.png)
Choose 
with 
.
,
.
as ![$\mathbb{Z}[\sqrt{5}]$](http://latex.artofproblemsolving.com/1/f/a/1faa8b2fafe42145f612b8ab6a04d5535fae96f6.png)
,
part which won't change much of the proof
![$\mathbb{Z}[\frac{1+\sqrt{5}}{2}]$](http://latex.artofproblemsolving.com/4/6/6/4668306b3338cf8aae04ce498dd72bec91eea7d3.png)
we can see that if 
then 
where 
and 
and using the minimal index notation one can see that 
'
we clearly have a constant as 
such that 
otherwise we can get our constant from above argument.
is multiple of 
are uniquely defined modulo 
for some 
.
and hence if order is less than 
then we can clearly get 
and thus our desired constant however in case order is equal to 
doesn't has a primitive prime divisor as 
then we can pick 
such that for all 
we have 
.
and 
Fibonacci number. It is easy to show that
The first equivalence follows from 
for all 
T
and Fermat little theorem. Now notice that 
This proves CLAIM 1. 
Notice that
Hence
for all 
.
for all 
.
Since there are only 
be the prime factors of 
and 
so that the sequence defined by 
,
and
has all its terms relatively prime to 
Now by taking this 
where ![\[x_n = F_{n-1}a + F_n b,\]](http://latex.artofproblemsolving.com/8/8/d/88dfc0d171ff6f8ab5f561bed8ebe62f29af53c4.png)
and since 
,
by Binet's thereom and Fermat's little theorem.
be the smallest positive integer such that 
,
mod 
.
,
can take at most 
values (since it repeats mod 
values, so there is some nonzero value mod 
.
.![\[x_n = F_{n-1}a + F_n b\equiv F_{n-1}-F_nc\pmod{p}.\]](http://latex.artofproblemsolving.com/1/5/8/158e9d575b34b2b8eaadcb793f17ec6f56a00fda.png)
If 
,
and 
(else 
for all 
,
by the selection of 
i.e 
,
to get a solution.)
and 
(
,
,
be a prime dividing 
or 
.
.
for 
.
for all 
.
.
,
.
.
for 
.
is periodic modulo 
such that 
.
.
.
.
,
.
.
if 
is nonzero 
.
:
,
,
,
,
,
,
,
,
.
,
.
.
and 
.
.
.
,
,
.
as the base case. We have
So, since 
,
.
such that when 
and 
,
is never a multiple of 
for all 
,
.
and the recursion can be characterized as usual in the form
and it clearly necessary that all of these should be nonzero mod 
which yields (after adding 
.
then 
.
,
and by CRT we're done.
and 
has all its terms nonzero modulo 
and 
.
modulo 
,
.
;
,
![\[\alpha^2\equiv \frac{1+4k+4k^2}{4}\equiv \frac{6+4k}{4}\equiv \frac{3+2k}{2}\equiv \alpha + 1\]](http://latex.artofproblemsolving.com/e/7/8/e7899695ba2688e6fe0d723cfdca04843f741e83.png)
This also implies 
.
and 
.
.
and 
already. Then for the induction step, we have for 
that![\[x_n\equiv x_{n-1}+x_{n-2}\equiv \alpha^{n-1}+\alpha^{n-2}\equiv \alpha^{n-2}(\alpha+1)\equiv \alpha^{n-2}\alpha^2\equiv \alpha^n\]](http://latex.artofproblemsolving.com/7/8/2/7827c04597e2fb78ba932c8d98108aaece03dd2e.png)
which completes the induction. Then, since 
and 
for all prime divisors 
construction:
