1. ## Number Theory

a) Suppose that n and k are positive integers with n congruent to k mod 40.
prove that 2^n is congruent to 2^k mod 55.

b) Prove that for any integer, n

n^11 is congruent to n mod 33.

2. Originally Posted by JCIR
a) Suppose that n and k are positive integers with n congruent to k mod 40.
prove that 2^n is congruent to 2^k mod 55.
If $n\equiv k(\bmod 40)$ then $n=k+40j$ for some $j$.
This means, $2^n = 2^{k+40j} = 2^k \left( 2^{40} \right)^j \equiv 2^k (\bmod 55)$.
Since $2^{40}\equiv 1(\bmod 55)$ by Euler's theorem.

b) Prove that for any integer, n

n^11 is congruent to n mod 33.
Consider the group $G=\mathbb{Z}_{33}^{\times}$.
This group is isomorphic to $\mathbb{Z}_3^{\times} \times \mathbb{Z}_{11}^{\times} \simeq \mathbb{Z}_2 \times \mathbb{Z}_{10}$.
Therefore, $G$ has exponent $10$ i.e. it means $x^{10} = 1$.
Thus, if $\gcd(n,33)=1$ it would mean $n^{10}\equiv 1(\bmod 33)$ so $n^{11}\equiv n(\bmod 33)$.
Now if $d=\gcd(n,33)\not = 1$ then it means $d= 3,11,33$.
If $d=33$ there is nothing to prove.
To complete the proof note that if $n=3,11$ this is true by mods.
Thus, if $d=3$ for example then $n=3m$ with $m$ relatively prime to $33$.
But then $n^{11} = 3^{11} m^{11} \equiv 3m = n(\bmod 33)$.
And with that this completes the proof.