by
JacobGuo, Aug 26, 2010, 12:20 AM
works:![\[5\cdot4^{10}+3\cdot10\equiv5\cdot4+3\cdot3=29\equiv1\pmod7.\]](http://latex.artofproblemsolving.com/d/5/1/d51a70b0bbac914b66455aa881ddc45f60fb4305.png)
I assume you accidentally thought that the period of the LHS was 
or something...
July 2014
June 2014
December 2013
August 2013
December 2012
February 2012
January 2012
November 2011
October 2011
August 2011
July 2011
April 2011
March 2011
January 2011
December 2010
November 2010
August 2010
July 2010
May 2010
February 2010
January 2010
December 2009
November 2009
October 2009
September 2009
July 2009
June 2009
May 2009
April 2009
defined as follows:![\[a_1=1,\quad a_{n+1}=\frac{1}{16}\left(1+4a_n+\sqrt{1+24a_n}\right).\]](http://latex.artofproblemsolving.com/6/0/5/605c07f2c7d8d8a3e3fd8e5d00059e56e0a54e1e.png)
for convenience. The recursion is equivalent to![\[(4b_{n+1}-b_n)^2=4(2b_{n+1}+b_n).\]](http://latex.artofproblemsolving.com/6/0/9/609346fad42b76fb77c978e68cb560145aacf253.png)
Let 
and 
,![\[x_n+y_n=6b_{n+1}=4y_{n+1}-2x_{n+1}\implies2x_{n+1}+x_n=4y_{n+1}-y_n.\]](http://latex.artofproblemsolving.com/c/a/1/ca1177966eec855c094dd2f25cd52ccddb5f469b.png)
Now![\[x_n^2=4y_n,\quad (2x_{n+1})^2=16y_{n+1}\implies(2x_{n+1}-x_n)(2x_{n+1}+x_n)=4(4y_{n+1}-y_n).\]](http://latex.artofproblemsolving.com/0/0/2/0025cfc1c63031d2f7154e260373a2a41903a803.png)
Note that![\[2x_{n+1}+x_n=4y_{n+1}-y_n=8b_{n+2}+2b_{n+1}-b_n.\]](http://latex.artofproblemsolving.com/6/a/1/6a14752d6d5f86f9a7c59d4727299cffb9a88166.png)
But![\[4b_{n+1}=b_n+1+\sqrt{1+6b_n}>b_n,\]](http://latex.artofproblemsolving.com/e/a/f/eaf815f467f1b65349e7d0ac11b7a0ad736eed84.png)
so![\[8b_{n+2}+2b_{n+1}-b_n>\frac12b_n+\frac12b_n-b_n=0.\]](http://latex.artofproblemsolving.com/9/4/e/94e43b87e4d13d0cd62703d626e99d72c1b03494.png)
Thus![\[2x_{n+1}-x_n=4=2x_{n+2}-x_{n+1},\]](http://latex.artofproblemsolving.com/0/7/3/073f86a7d4b90f47770cfc87a6926fa47e0b5758.png)
so![\[8b_{n+2}-6b_{n+1}+b_n=8b_{n+3}-6b_{n+2}+b_{n+1}\]](http://latex.artofproblemsolving.com/d/3/9/d39e233651d52f2924598f6deed4b2f5496c2c13.png)
and![\[8b_{n+3}-14b_{n+2}+7b_{n+1}-b_n=0.\]](http://latex.artofproblemsolving.com/3/7/b/37b1d1f51c0e150f76a1c692e4a61466e7451955.png)
The characteristic equation of this is 
,
with 
,
such that![\[Aa^x+Bx\equiv c\pmod{n}.\]](http://latex.artofproblemsolving.com/1/7/e/17e450fa96233367b32ef3158d114c3a67287c9e.png)
;
is trivial. Now note that it suffices to find infinitely many ![\[AB^{-1}a^x+x\equiv cB^{-1}\pmod{n}.\]](http://latex.artofproblemsolving.com/8/4/2/84201d403191b430aa088cbdd8b8cabfd704f1fe.png)
Define the positive integers 
such that![\[A'-AB^{-1}\equiv c'-cB^{-1}\equiv0\pmod{n}.\]](http://latex.artofproblemsolving.com/1/9/5/1950e2116a6f1d3eca5d290632396bb7b83338a2.png)
By the inductive hypothesis some 
may not be coprime)![\[\gcd(a^x,\phi(n))=\gcd(a^{x+1},\phi(n))\]](http://latex.artofproblemsolving.com/0/7/d/07d6f379933f0ab6b8c1e0c85863055657ee78f3.png)
and![\[A'a^x+x\equiv c'\pmod{\phi(n)}.\]](http://latex.artofproblemsolving.com/b/f/f/bff196ed786cf9beb9c6f701f4d2bb7a81cdf93e.png)
Since![\[A'a^x+x\equiv A'a^{x+r\phi(n)\phi(\phi(n))}+x+r\phi(n)\phi(\phi(n))\pmod{\phi(n)},\]](http://latex.artofproblemsolving.com/c/e/8/ce834578ce7b716eb41701150474ba69747ec85f.png)
we can choose sufficiently large 
with (let 
)![\[a^{sn\phi(n)+c'-A'a^{x'}}\equiv a^{x'}\pmod{n},\]](http://latex.artofproblemsolving.com/0/7/e/07e53c7058dcc57d72266452710a7df49c91b6a3.png)
![\[sn\phi(n)+c'-A'a^{x'}>x',\]](http://latex.artofproblemsolving.com/1/6/4/164c600f3f34da3103805a5c35e23211b6172c6b.png)
and![\[\gcd(a^{x'},n)=\gcd(a^{x'+1},n).\]](http://latex.artofproblemsolving.com/a/2/4/a24a4c939da7cb2c109e68417f8b9fa4337908bf.png)
(Again, 
may not be coprime.) Finally, we have![\[A'a^{sn\phi(n)+c'-A'a^{x'}}+sn\phi(n)+c'-A'a^{x'}\equiv A'a^{x'}+c'-A'a^{x'}\equiv c'\pmod{n}.\]](http://latex.artofproblemsolving.com/e/b/b/ebbc79cea780b9e68baf28d572afa3558d801361.png)
Letting 
,![\[A'a^{t+kn\phi(n)}+t+kn\phi(n)\equiv c'\pmod{n}\]](http://latex.artofproblemsolving.com/6/b/5/6b542b4c8a956ffce69170449a626170d35023c9.png)
for all positive 
,
