there is a prove that there is no $2^n$ that is divisible by 5?
prove: $2^n$ is not divisible by 5 for any $n$
-
2Since there will be no $5$ in prime factorization of $2^n$. – 2010-12-23
4 Answers
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$.
-
1In fact something even more general holds: If $R$ is an [integral domain](http://en.wikipedia.org/wiki/Integral_domain) and $p,q \in R$ are non-associated [prime elements](http://en.wikipedia.org/wiki/Prime_element#Divisibility.2C_prime_and_irreducible_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) – 2010-12-23
-
0@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. – 2010-12-23
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.
-
2Or multiply both sides by $ 2^{-1} \equiv 3 \pmod{5} $. – 2010-12-23
-
0That'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. – 2010-12-23
-
2@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$? – 2010-12-23
-
0@Mariano: The point of writing it the way that I did was was to nudge the OP to discover the relation between inverses and the Bezout relation. Not only is that not obscure, but it is a fundamentally sound way to teach - much better than handing answers to students on a silver platter. The joy of discovery goes a long way towards reinforcing true understanding. – 2010-12-23
-
2But, 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. – 2010-12-23
-
1@Bill: In Scotland, there is at least one sheep, at least one side of which looks black! :) – 2010-12-23
HINT: For every modulus, all relatively prime integers are a multiplicative group.
(Without this, number theory would be quite pointless)