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 $\displaystyle n\equiv k(\bmod 40)$ then $\displaystyle n=k+40j$ for some $\displaystyle j$.
This means, $\displaystyle 2^n = 2^{k+40j} = 2^k \left( 2^{40} \right)^j \equiv 2^k (\bmod 55)$.
Since $\displaystyle 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 $\displaystyle G=\mathbb{Z}_{33}^{\times}$.
This group is isomorphic to $\displaystyle \mathbb{Z}_3^{\times} \times \mathbb{Z}_{11}^{\times} \simeq \mathbb{Z}_2 \times \mathbb{Z}_{10}$.
Therefore, $\displaystyle G$ has exponent $\displaystyle 10$ i.e. it means $\displaystyle x^{10} = 1$.
Thus, if $\displaystyle \gcd(n,33)=1$ it would mean $\displaystyle n^{10}\equiv 1(\bmod 33)$ so $\displaystyle n^{11}\equiv n(\bmod 33)$.
Now if $\displaystyle d=\gcd(n,33)\not = 1$ then it means $\displaystyle d= 3,11,33$.
If $\displaystyle d=33$ there is nothing to prove.
To complete the proof note that if $\displaystyle n=3,11$ this is true by mods.
Thus, if $\displaystyle d=3$ for example then $\displaystyle n=3m$ with $\displaystyle m$ relatively prime to $\displaystyle 33$.
But then $\displaystyle n^{11} = 3^{11} m^{11} \equiv 3m = n(\bmod 33)$.
And with that this completes the proof.