0

Say I have 5^(52) mod 22

How do I reduce this?

I know if 22 was a prime number, then I could simply I could simply reduce 5^(22) * 5^(22) * 5^(8) which would become 5^(8) mod 22 but that doesn't work in this case.

user2827048
  • 167

2 Answers2

1

$\begin{eqnarray}{\bf Hint} &&{\rm mod}\ 11\!:\ 5^{10}\equiv 1\ \ \rm by\ \ Fermat's\ \ little\ Theorem\\ &&{\rm mod}\ 2\!:\ \ \ 5^{10}\equiv 1\ \ {\rm by}\ \ 5\equiv 1\\ \Rightarrow&&{\rm mod}\ 22\!:\ \color{#c00}{5^{10}\equiv 1}\,\Rightarrow\,\,5^{52} = 5^2 \color{#c00}{(5^{10})}^5 \equiv 25\color{#c00}{(1)}^5\equiv 3\end{eqnarray}$

Bill Dubuque
  • 272,048
0

Hint: $5^2 \equiv 3$, and $3^3 \equiv 5$, which means $5^{6}\equiv 5$.

Lord Soth
  • 7,750
  • 20
  • 37
  • Ok, so if I determine that 5^2 is congruent to 3 then can I just say 5^52 is congruent to 3 without determining that 5^6 is congruent to 5 because 5^52 = 5^2 * 5^2.....5^2 – user2827048 Mar 19 '14 at 00:44
  • @user2827048 You can only say $5^{52} \equiv 3^{26}$ given that $5^2\equiv 3$. – Lord Soth Mar 19 '14 at 00:46
  • Ok, here's how I solved it using what you described: 5^52 is really just (5^2)^26 making it 3^26. 3^26 can be rewritten as 3^21 and 3^5 reducing to (3^3)^7 * 3^3 * 3^2. This then becomes 5^7 * 5 * 3^2. This is 5^8 * 32. This can be rewritten as (5^2)^4 3^2 which is 3^4 * 3^2. This is 3^6. which is 3^3 * 3^3. This is 5 * 5 which is 25. 25 mod 22 is 3. – user2827048 Mar 19 '14 at 01:21