Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

there is a prove that there is no $2^n$ that is divisible by 5?

share|improve this question
2  
Since there will be no $5$ in prime factorization of $2^n$. –  Quixotic Dec 23 '10 at 13:44
add comment

4 Answers 4

up vote 13 down vote accepted

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

share|improve this answer
1  
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
2  
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
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$? –  Mariano Suárez-Alvarez Dec 23 '10 at 14:30
2  
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
1  
@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
show 1 more comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.