finding remainder by using fermat's little theorem or euler's totient

Question

I am trying to carry on for the following equation but I stuck with a big number that still needs to be smaller to calculate without calculator.

$\ 331^{51}\mod 49$

Since the $\phi(49)=42$, I carried on the problem as follows:

$=\ 331^{42}.331^{9}\mod 49$

which $331^{42}=1$, so;

$=\ 331^{9}\mod 49$

Since $331/49$ remains $37$ problem becomes;

$=\ 37^{9}\mod 49$

$=\ (-12)^{9}\mod 49$

$=\ (-12)^{8}.(-12)\mod 49$

Since 8 is even;

$=\ (12)^{8}.(-12)\mod 49$

...

.(a bunch of conversions)...

...

Finally I have found this (which is checked via wolframalpha and it is correct);

$=\ (2)^{29}.(23)\mod 49$

But it is still too big to calculate manually. So I wonder maybe one of you guys have another idea? Especially, I want to know whether I can use $49$ as $7*7$ and create two different modular equations and solve them in a way? maybe with CRT maybe with another method?

Answer 1

If $2^{42} \equiv 1\mod 49$ then $2^{21}$ is probably equiv to $\pm 1\mod 49$.

$2^{21} = (2^7)^3=128^3 \equiv 30^3 =27000 = 54*500=54*490 + 54*10\equiv 5*10=50\equiv 1\mod 49$.

So $2^{29}\equiv 2^8=2*2^7\equiv 2*30=60\equiv 11 \mod 49$.

$11*23 = 253 = 250 + 3 = 50*5 + 3 \equiv 5*3 = 8 \mod 49$.

======

"Especially, I want to know whether I can use 49 as 7∗7 and create two different modular equations and solve them in a way?"

That's a clever idea. Just... be careful.

$2^6\equiv 1 \mod 7$ so $2^6 \equiv 1+ 9*7\equiv 1+2*7 \mod 49$. $2^{30}=(2^6)^5 \equiv 1 + 5*2*7\mod 49$. ($(1+2*7)^5 = \sum {5 \choose i}(2*7)^i$ and $49|(2*7)^i; i\ge 2$). So $2^{30}\equiv 1+5*2*7\mod 49\equiv 2^{30}\equiv 1+3*7\equiv 22 \mod 49$. $1\equiv 50\equiv 2*25 \mod 49$ so $2^{-1}\equiv 25\mod 49$. So $2^{29} \equiv 22*25 \equiv 11*50\equiv 11\mod 49$.

So that works too.

====

Since $2^{42} \equiv 1 \mod 49$ it's probably useful to figure the $2^{k;k|42}$ are. And what sort of roots they are.

$2^3 \equiv 8 = \sqrt{49} + 1$ is a 14th root of 1. Maybe a (square or 7th root)

$2^6 \equiv 2*\sqrt{49} + 1 \equiv 15$ is a 7th root of 1. (7 is prime so can't be any lower root of 1)

$2^{21}\equiv (\sqrt{49} + 1)^7 \equiv 7*\sqrt{49} + 1\equiv 1\mod 49$ so $2^3$ was a 7th root of 1.

Hennce $2^7$ is a 3rd root of 1.

.....

oh, for goodness sake. $2^3 = 7 + 1$. That make everything easier! $2^{3m+k} = 2^k(7*(m\% 7) + 1)\mod 49$. So $2^{29} = 2^{3*9+2} \equiv 4*(7*2 +1)\equiv 60 \equiv 11 \mod 49$.

Answer 2

Hint:

Using binomial theorem,

$$(-12)^7=(2-14)^7\equiv2^7\pmod{49}$$

and $$12^2\equiv-3\pmod{49}$$