such that 
, where 
are non-negative reals such that 
.
.
a tangencial quadrilateral that is not a rhombus, let 
be lengths of tangents from 
to the incircle of the quadrilateral which center is 
.
be the midpoints of 
resp. Prove that![\[ \frac{MI}{IN}=\frac{a+c}{b+d} \]](http://latex.artofproblemsolving.com/e/7/0/e709acb8b17c0466a385ba8e7a89bb1bf16c72af.png)
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 
such that 
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:
