0

I can't seem to even find an example of this, so if anyone could help me with an example or how to do it (I am doing this purely for myself) it would be greatly appreciated:

Use Euler's phi function to determine $11^{20162} mod 31850$

moony
  • 720

1 Answers1

2

Factorising, $$31850=2\times5^2\times7^2\times13\ ,$$ and so $$\phi(31850)=(2^0\times1)\times(5^1\times4)\times(7^1\times6)\times(13^0\times12)=10080\ .$$ Now $11$ is relatively prime to $31850$, so by Euler's theorem $$11^{10080}\equiv1\pmod{31850}\ ,$$ and hence $$11^{20162}=(11^{10080})^2\times11^2\equiv1^2\times11^2\equiv121\pmod{31850}\ .$$

Addendum. Answers to questions in comments.

  • Factorising $31850$ easily: obviously $10=2\times5$ is a factor, and the quotient ends in $5$ so it has a factor of $5$ again. Dividing out leaves $637$ which is small enough to be easy, especially if you see immediately that $7$ is a factor.
  • The $121$ is just $11^2=11\times11$.
David
  • 82,662
  • 2
    Small typo in 3rd display. – Gerry Myerson Oct 02 '14 at 13:07
  • ok sorry to be so annoying, but i do not really understand that at all. How did you factor 31850 so easily? and where did the 121 come from? – moony Oct 02 '14 at 13:20
  • @moony He uses Euler's theorem : http://en.wikipedia.org/wiki/Euler's_theorem – Marc Bogaerts Oct 02 '14 at 13:58
  • 1
    Typo fixed thanks @Gerry - at least the congruence I had was true, if trivial ;-) – David Oct 03 '14 at 00:17
  • @moony, see updated answer. – David Oct 03 '14 at 00:21
  • @moony It's not important to factor that by hand. You can just look it up online if you like. The point is that $a^{\phi(31850)} = 1 \ (\text{mod} 31850)$ for $(a, 31850) = 1$ by the generalization of Fermat's Little Theorem's known as Euler's theorem. http://en.wikipedia.org/wiki/Euler's_theorem – user4894 Oct 03 '14 at 01:10