Modular arithmetic (how to solve 15^{323} mod 51 if gcd(15,51)=3?)

[canvas]

[math]15^{323}\mod\,51\\\\\text{how to solve it if}\,\,\red{\gcd(15,51)=3}\,\,?[/math]

 

[BigBeachBanana]

[math]15^{323}\mod\,51\\\\\text{how to solve it if}\,\,\red{\gcd(15,51)=3}\,\,?[/math]

Do you know Euler's totient function, [imath]\phi(n)[/imath]?

[math]x^y \mod n \equiv x^{y \mod \phi(n)} \mod n[/math]

 

[blamocur]

[math]15^{323}\mod\,51\\\\\text{how to solve it if}\,\,\red{\gcd(15,51)=3}\,\,?[/math]

Can you show that if [math]a\equiv b \mod p[/math] then for all natural [imath]k[/imath]: [math]ka \equiv kb \mod kp[/math] ?

 

[AvgStudent]

Do you know Euler's totient function, [imath]\phi(n)[/imath]?

[math]x^y \mod n \equiv x^{y \mod \phi(n)} \mod n[/math]

I was able to solve this using @BigBeachBanana 's method:
[math]15^{323} \equiv 15^{323 \mod \phi(51)} \equiv 15 ^{323 \mod 32} \equiv 15^{3} \equiv 66\times 51 + 9 \equiv 9 \mod 51[/math]

Can you show that if [math]a\equiv b \mod p[/math] then for all natural [imath]k[/imath]: [math]ka \equiv kb \mod kp[/math] ?

[imath]a\equiv b \mod p \implies p|(a-b)[/imath]. So, [imath]p[/imath] divides [imath]k(a-b) = ak-bk[/imath].
Therefore, [imath]ak \equiv bk \mod k[/imath]

Is it supposed to be [imath]\mod k[/imath] or [imath]\mod kp?[/imath] Also, I don't see where you're going with this can you expand?

Please note that I'm not the OP. This thread seems abandoned so I just took an interest.

 

[blamocur]

Is it supposed to be mod  k\mod kmodk or mod  kp?\mod kp?modkp? Also, I don't see where you're going with this can you expand?

It is supposed to be [imath]\mod kp[/imath].

I was thinking of reducing this problem to [imath]\mod 17[/imath]:
[math]3^{322} = 3^{320} \cdot 9 \equiv 9 \mod 17[/math]Since [imath]5^{17} \equiv 5 \mod 17[/imath]:
[math]5^{323} = 5^{17\cdot 19} \equiv 5^{19} \equiv 5 \cdot 5^2\mod 17 \Rightarrow 5^{323} \equiv 125 \mod 17 \Rightarrow 5^{323} \equiv 6 \mod 17[/math][math]3^{322}5^{323} \equiv 9\cdot 6 \mod 17 \Rightarrow 3^{322} 5^{323} \equiv 3 \mod 17[/math]Multiplying all sides by 3 we get:
[math]15^{323} = 3\cdot3^{322}\cdot 5^{323} \equiv 3\cdot3 \mod 3\cdot17[/math]I.e., the answer is 9.