BÁSICO
Já que
, pelo teorema de Euler-Fermat temos que
; por outro lado,
é a ordem de
módulo
já que
e se
temos
e assim
não divide
. Como
temos portanto
.
![mdc(a,a^n-1)=1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_d81fca55dcc6d6edd5cdb314b817d610.gif?w=640&ssl=1)
![a^{\phi(a^n-1)}\equiv 1 \pmod{a^n-1}](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_0e2e5f0a9a41c450c08b39b723d50491.gif?w=640&ssl=1)
![n](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif?w=640&ssl=1)
![a](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_0cc175b9c0f1b6a831c399e269772661.gif?w=640&ssl=1)
![a^n-1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_0356a41a4981e8576f923aa6acc095b0.gif?w=640&ssl=1)
![a^n\equiv1\pmod{a^n-1}](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_b4c9314d91d84a540bbce44c7ce9a5c7.gif?w=640&ssl=1)
![0<t<n](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_c02f1629f344cb87d93a363a7c8f4758.gif?w=640&ssl=1)
![0<a^t-1<a^n-1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_a7faed4f10f2581b030e737bb65ead18.gif?w=640&ssl=1)
![a^n-1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_0356a41a4981e8576f923aa6acc095b0.gif?w=640&ssl=1)
![a^t-1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_5668bcd377d8501c7b7a3a5e6692ed89.gif?w=640&ssl=1)
![a^j\equiv1\pmod{m} \Rightarrow ord_m a|j](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_5f7e27f5ac7f52647efba85e54bd930a.gif?w=640&ssl=1)
![n|\phi(a^n-1)](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_7c694cc2f0296dd99642bc5c782cb8fa.gif?w=640&ssl=1)
INTERMEDIÁRIO
Comece notando que
n!+1)" />. Se
primo, então pelo Teorema de Wilson temos
. Se
não é primo, então para cada fator primo
de
, teremos
!. Com isso, podemos concluir que nesse caso
.
![mdc(n!,n!+1)=1\Rightarrow f(n)=mdc((n+1)!,n!+1)=mdc(n+1,<wbr data-recalc-dims=](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_3f0f5ac14e2355dc8a0f2e47363cd5a0.gif?w=640&ssl=1)
![n+1=p](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_3b2fb8bfae8f08f10698900732c3b842.gif?w=640&ssl=1)
![n!\equiv(p-1)!\equiv -1 \pmod{p} \Rightarrow n+1|n!+1\Rightarrow f(n)=n+1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_993d696e159593994057502284176c53.gif?w=640&ssl=1)
![n+1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_40b85027598d87611b1c8d5d11e46812.gif?w=640&ssl=1)
![q](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_7694f4a66316e53c8cdd9d9954bd611d.gif?w=640&ssl=1)
![n+1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_40b85027598d87611b1c8d5d11e46812.gif?w=640&ssl=1)
![q<n+1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_5188a7cd682731414d5b3230dca1c323.gif?w=640&ssl=1)
![\Rightarrow q\le n \Rightarrow q|n](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_d1acaae38aae209106deb5dd8051f6c6.gif?w=640&ssl=1)
![f(n)=1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_b9ad66ff822e00497667f0a726ae956f.gif?w=640&ssl=1)
AVANÇADO
Observe que:
![a_{n+1}=\dfrac{a_n}{2} + \dfrac{2}{a_n} = \dfrac{a_n^2+4}{2a_n}](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_8b020239297828a3a08dc9c2ce9e5233.gif?w=640&ssl=1)
![\Rightarrow a_{n+1}\pm 2=\dfrac{a_n^2\pm 4a_{n}+4}{2a_{n}}=\dfrac{(a_{n} \pm 2)^2}{2a_n}](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_143f114b20e6e33910c745c0b3710dd7.gif?w=640&ssl=1)
Assim, temos que:
![\dfrac{a_{n+1}+2}{a_{n+1}-2}=(\dfrac{a_n+2}{a_n-2})^2](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_4ce7f905292c132fd715fafd85c79d26.gif?w=640&ssl=1)
![n\ge1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_faf1b3a30453e631b14c4b627225001e.gif?w=640&ssl=1)
Assim, é fácil ver que, por indução:
![\dfrac{a_n+2}{a_n-2}=(\dfrac{a_1+2}{a_1-2})^{2^{n-1}}=(\dfrac{4+2}{4-2})^{2^{n-1}} = 3^{2^{n-1}}](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_6c28b56bda9f876daa5e638a44faea2a.gif?w=640&ssl=1)
Com isso, concluímos que:
![a_n=2(\dfrac{3^{2^{n-1}}+1}{3^{2^{n-1}}-1})](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_3293ed1d07861fdedd25d31948228650.gif?w=640&ssl=1)
![n\ge 1](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_1d0fe3ad28ed27546808efeec5c626a9.gif?w=640&ssl=1)