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

[canvas]

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

 

[BigBeachBanana]

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

Do you know Euler's totient function, $\phi(n)$?

$$x^y \mod n \equiv x^{y \mod \phi(n)} \mod n$$

 

[blamocur]

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

Can you show that if $$a\equiv b \mod p$$ then for all natural $k$: $$ka \equiv kb \mod kp$$ ?

 

[AvgStudent]

Do you know Euler's totient function, $\phi(n)$?

$$x^y \mod n \equiv x^{y \mod \phi(n)} \mod n$$

I was able to solve this using @BigBeachBanana 's method:
$$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$$

Can you show that if $$a\equiv b \mod p$$ then for all natural $k$: $$ka \equiv kb \mod kp$$ ?

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

Is it supposed to be $\mod k$ or $\mod kp?$ 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 $\mod kp$.

I was thinking of reducing this problem to $\mod 17$:
$$3^{322} = 3^{320} \cdot 9 \equiv 9 \mod 17$$Since $5^{17} \equiv 5 \mod 17$:
$$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$$$$3^{322}5^{323} \equiv 9\cdot 6 \mod 17 \Rightarrow 3^{322} 5^{323} \equiv 3 \mod 17$$Multiplying all sides by 3 we get:
$$15^{323} = 3\cdot3^{322}\cdot 5^{323} \equiv 3\cdot3 \mod 3\cdot17$$I.e., the answer is 9.