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)

Printable View

- Dec 2nd 2008, 02:25 AMfelixmcgradynumber 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 AMPaulRS
**1.**Suppose $\displaystyle q$ is a prime divisor of $\displaystyle 2^{p}-1$ then $\displaystyle

2^p \equiv 1\left( {\bmod .q} \right)

$ and thus, by Lagrange's Theorem, the order of $\displaystyle 2$ divides $\displaystyle

\left| {\mathbb{Z}_q ^ \times } \right|=q-1

$. (1)

Suppose $\displaystyle s>1$ is the order of $\displaystyle 2$, it cannot be 1 for otherwise $\displaystyle 2\equiv{1}(\bmod.q)$, and since $\displaystyle

2^p \equiv 1\left( {\bmod .q} \right)

$ the order must divide $\displaystyle p$, but since $\displaystyle p$ is prime this implies that $\displaystyle s=p$ that is the order of $\displaystyle 2$ is $\displaystyle p$. So, by (1), $\displaystyle p|(q-1)$ thus $\displaystyle q-1\geq{p}$ thus $\displaystyle q>p$

**2.**By induction, it's true for k=1, so let's assume it's true for some $\displaystyle k\in

\mathbb{Z}^ +

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

By hypothesis $\displaystyle

2^{3^{k - 1} } \equiv - 1\left( {\bmod .3^k } \right)

$ so $\displaystyle

2^{3^{k - 1} } = 3^k \cdot s - 1

$ now: $\displaystyle

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: $\displaystyle

2^{3^k } \equiv - 1\left( {\bmod .3^{k + 1} } \right)

$

In fact 2 is a primitive root module $\displaystyle 3^k$ for all $\displaystyle k\in

\mathbb{Z}^ +

$ - Dec 3rd 2008, 04:31 PMThePerfectHacker
If $\displaystyle a\equiv b(\bmod p^k) \implies a^p \equiv b^p (\bmod p^{k+1})$*.

You can prove this result by induction.

Say $\displaystyle 2^{3^{t-1}} \equiv -1 (\bmod 3^t)$ then $\displaystyle 2^{3\cdot 3^{t-1}} \equiv (-1)^3 = -1 (\bmod 3^{t+1})$ and so $\displaystyle 2^{3^t} \equiv -1(\bmod 3^{t+1})$.

*)This can be proven by binomial expanding as**PaulRS**did.