0

I want to calculate:

$2^{33} \mod 25$

Therefore I calculate first the Euler's phi function of 25:

$\phi(25) = 5^{2-1} (5-1)$ = 20

Now I can continue with Fermat's little problem:

$2^{33} \mod 25$ = $(2^{20} * 2^{13}) \mod 25 \equiv 2^{13} \mod 25$

How can I proceed to simplify the result? I tried the following 2 approaches and I'm not sure what kind of operations are allowed and which are not. In both ways, I'll get the same result but it is wrong:

1. Approach

$2^{13} \mod 25 \equiv ((2^5 \mod 25)^2 * 2^3) \mod 25 \equiv$
$\equiv ((7^2 \mod 25) * (2^3 \mod 25)) \mod 25 \equiv 24 * 7 \mod 25 \equiv$
$\equiv 168 \mod 25 = 18$

2. Approach

$2^{13} \mod 25 \equiv ((2^5 \mod 25)^2 * 2^3) \mod 25 \equiv$
$\equiv 7^2 * 2^3 \mod 25 \equiv 1568 \mod 25 = 18$

nikola42
  • 3
  • 2

2 Answers2

2

Your approach is right, but the next-to-last steps on both your calculations are wrong: in the first approach, $2^3\bmod{25}=8\bmod25$, and not $7$, so $$7^2*2^3\bmod25=24*8\bmod25=192\bmod25=17\bmod25$$.

In the second approach you susbsituted $7^2*2^3$ by 1568, which I don't understand.

Luiz Cordeiro
  • 18,513
1

What I would do....

Express $13$ as a sum of powers of $2$: $13 = 8 + 4 + 1$

$2^4 \equiv 16 \pmod{25}$

$2^8 \equiv 256 \equiv 6 \pmod{25}$

$2^{13} \equiv 6 \times 16 \times 2 \equiv -4 \times 2 \equiv 17 \pmod{25}$

Steven Alexis Gregory
  • 26,769