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

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < December 1 ! width="25%" align="center"|<< Nov | December | Jan >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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 $\varphi (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^{\varphi (n)+1}\equiv a(\mathrm{mod}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)

Template:Resolved