prove: $2^n$ is not divisible by 5 for any $n$ there is a prove that there is no $2^n$ that is divisible by 5?
 A: HINT: Use the fact that the powers of $2$ end with $2,4,8,6$ and for divisibility for 5 last digit has to end with either 5 or $0$.
A: HINT $\ $ By Gauss's algorithm for computing inverses modulo a prime $\rm\: 2\:n+1\:$ (here $5$) we have:
$\rm\quad\ \ \displaystyle \frac{1}2\ \equiv\ \frac{n+1}{2\:(n+1)}\ \equiv\ n+1\ \ (mod\:\ 2\:n+1)\:.\quad $ Hence $\rm\ 2^n \equiv 0\ $ times $\ (1/2)^n\ $ yields $\rm\ 1\equiv 0\ \Rightarrow\Leftarrow$  
More generally any integer $\rm\:a\:$ coprime to $\rm\:d\:$ can be constructively inverted $\rm\:(mod\ d)\:$ by employing the extended Euclidean algorithm to find a Bezout relation $\rm\ a\ b + c\ d = 1\ \Rightarrow\ a\ b \equiv 1\ \:(mod\ d)\:.$
This is very closely related to "rationalizing denominators", e.g. see my sci.math post for further remarks on rationalizing denominators 
and computing inverses via (minimal) polynomials, the extended Euclidean 
algorithm, Grobner bases, resultants, norms, etc. 
A: This is a special case of the fundamental theorem of arithmetic: every integer can be uniquely written as a product of primes. Since both 2 and 5 are primes, an identity like $2^n = 5k$ for $k\in \mathbb{N}$ would contradict the uniqueness of prime factorisation.
Exercise: more generally, find a necessary and sufficient criterion on integers $m$ and primes $p$ for $m^n$ to be divisible by $p$ for some $n$. Further prove that if divisibility holds for some $n$, then it holds for all natural $n>0$.
A: HINT: For every modulus, all relatively prime integers are a multiplicative group.
(Without this, number theory would be quite pointless)
