Number Theory or Algebra? Part 8

Hi Shreyash, I also don't know modular arithmetic, but I did it without it. First of all, 2^24 can be written as 256^3 or (127*2+2)^3 this will give a remainder of 8 when divided by 127 (hope you know why!). Sorry for not using LaTeX, had to do lots of Maths home work!!!!

Notice that 2^7 = 128, if you divide it by 127 a remainder 1. in modular arithmetic can be written as 2^7 = 128= 1 (mod 127).

It's one of congruence's properties. I will prove it below. Theorem: If $m$ is a positive integer, $m>0$ , $a, b, c \in I^{+}$ , then if $a \equiv b (mod m)$ , then $a^{k} \equiv b^{k} (mod m)$

Proof : If $a \equiv b (mod m)$ , then $m|a-b$

Suppose that $\frac{a - b}{m} = c$ , when $c$ is a positive integer.

Then, $a - b = mc ---(*)$

On the other hand, $a^{k} - b^{k} = (a - b)(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1})$

Subsituting Equation $(*)$ , $a^{k} - b^{k} = (mc)(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1})$

Thus, $\frac{a^{k} - b^{k}}{m} = c(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1})$

Since $c, (a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1}) \in I^{+},$

So since $c(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1}) \in I^{+},$

So since $m|a^{k} - b^{k},$

$\therefore \boxed{a^{k} \equiv b^{k} (mod m)}$ .

Easily speaking, when the first number is congruent to the second with a mod, the first number raised to any power will be congruent to the second raised to the same power, with the same mod.

So, in this case :

$2^{7} \equiv 1 (mod 127)$

$(2^{7})^{3} \equiv 1^{3} (mod 127)$

$\therefore 2^{21} \equiv 1 (mod 127)$