# number theory

• Dec 2nd 2008, 02:25 AM
number theory
thanks for helpin me. guys(Bow)

1. let p be a prime, show that every prime divisor of (2^p) -1 is greater than p.

2. let n= 3^(t-1). show that 2^n = -1 (mod 3^t)
• Dec 2nd 2008, 03:39 AM
PaulRS
1. Suppose $q$ is a prime divisor of $2^{p}-1$ then $
2^p \equiv 1\left( {\bmod .q} \right)
$
and thus, by Lagrange's Theorem, the order of $2$ divides $
\left| {\mathbb{Z}_q ^ \times } \right|=q-1
$
. (1)

Suppose $s>1$ is the order of $2$, it cannot be 1 for otherwise $2\equiv{1}(\bmod.q)$, and since $
2^p \equiv 1\left( {\bmod .q} \right)
$
the order must divide $p$, but since $p$ is prime this implies that $s=p$ that is the order of $2$ is $p$. So, by (1), $p|(q-1)$ thus $q-1\geq{p}$ thus $q>p$

2. By induction, it's true for k=1, so let's assume it's true for some $k\in
\mathbb{Z}^ +

$
we'll show that this implies the assertion for $k+1$

By hypothesis $
2^{3^{k - 1} } \equiv - 1\left( {\bmod .3^k } \right)
$
so $
2^{3^{k - 1} } = 3^k \cdot s - 1
$
now: $
2^{3^k } = \left( {3^k \cdot s - 1} \right)^3 = 3^{k + 1} \cdot t - 1
$
( see the terms in the binomial expansion), thus: $
2^{3^k } \equiv - 1\left( {\bmod .3^{k + 1} } \right)
$

In fact 2 is a primitive root module $3^k$ for all $k\in
\mathbb{Z}^ +
$
• Dec 3rd 2008, 04:31 PM
ThePerfectHacker
Quote:

If $a\equiv b(\bmod p^k) \implies a^p \equiv b^p (\bmod p^{k+1})$*.
Say $2^{3^{t-1}} \equiv -1 (\bmod 3^t)$ then $2^{3\cdot 3^{t-1}} \equiv (-1)^3 = -1 (\bmod 3^{t+1})$ and so $2^{3^t} \equiv -1(\bmod 3^{t+1})$.