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