# 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?

-
Since there will be no $5$ in prime factorization of $2^n$. – Quixotic Dec 23 '10 at 13:44

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$.

-
In fact something even more general holds: If $R$ is an integral domain and $p,q \in R$ are non-associated prime elements then $p \nmid q^n$ for all $n \geq 1$. The proof of course goes by induction on $n$ (I shall not write it here as that would essentially give a complete answer to the original question) – kahen Dec 23 '10 at 11:45
@Kahen: You don't need $\rm\:q\:$ prime, only that prime $\rm\:p\nmid q\:$. By definition, a prime divides a product iff it divides one of the factors. – Bill Dubuque Dec 23 '10 at 15:09

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$.

-

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.

-
Or multiply both sides by $2^{-1} \equiv 3 \pmod{5}$. – Mitch Schwartz Dec 23 '10 at 14:05
That's equivalent: I use $\ 1/2 \equiv -2 \equiv 3$. The point of writing it out as above is that it explicitly shows how the inverse of $2$ arises from writing $1$ as a linear combination of $5$ and $2$, i.e. the fundamental Bezout linear representation of the gcd. – Bill Dubuque Dec 23 '10 at 14:15
@Bill, your "since $x=5x-2(2x)$ may show that, but it is a completely obscure observation unless you already know you need to make the inverse appear. In that case, why no just multiply by $3$? – Mariano Suárez-Alvarez Dec 23 '10 at 14:30
But, Bill: there are two points to be made: first, that one needs to multiply by the inverse, second, that with enough ingenuity one can use the Bezout relation to find it. But "since $x=5x-2(2x)$" is only clear to someone who already understood both things, or a cryptic hint that one should understand them. I agree to disagree here with you, as we essentially always do in matters of pedagogy. – Mariano Suárez-Alvarez Dec 23 '10 at 15:17
@Bill: In Scotland, there is at least one sheep, at least one side of which looks black! :) – Mariano Suárez-Alvarez Dec 23 '10 at 22:55

HINT: For every modulus, all relatively prime integers are a multiplicative group.
(Without this, number theory would be quite pointless)

-