Wikipedia:Reference desk/Archives/Mathematics/2014 December 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 2

Euler's theorem

Hello, I am reading Elementary number theory by Barton, section 7.3, Euler's theorem and have a mental block. It asks me to prove $a^{37}=a\,(mod1729)$. I have verified this numerically so I know it's true. He gives me the hint that 1729=7.13.19. I get $\phi (1729)=1296=36^{2}$ so Euler's theorem gives me $a^{36\times 36}=a(mod1729)$. So then $(a^{36})^{37}=a^{37}$ but there I get stuck. I have just found out that $a^{36}$ is not equal to 1 for any a except a=1. I don't seem to be able to extract anything about $a^{37}$. I am making very heavy weather of this, what am I missing? Robinh (talk) 04:10, 2 December 2014 (UTC)

You're using the hint wrong. What is relevant is that 37 mod φ(7) = 37 mod φ(13) = 37 mod φ(19) = 1, which means $a^{37}\equiv a^{\phi (n)+1}\equiv a{\pmod {n}}$, for n = 7, 13, and 19. (See the article on the Chinese remainder theorem if the significance of that is not immediately obvious to you.) --173.49.79.100 (talk) 05:56, 2 December 2014 (UTC)

Resolved