number theory

**felixmcgrady** · December 2nd 2008, 02:25 AM

thanks for helpin me. guys

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)

**PaulRS** · December 2nd 2008, 03:39 AM

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}^ + $

**ThePerfectHacker** · December 3rd 2008, 04:31 PM

Originally Posted by felixmcgrady

2. let n= 3^(t-1). show that 2^n = -1 (mod 3^t)

If $a\equiv b(\bmod p^k) \implies a^p \equiv b^p (\bmod p^{k+1})$ *.

You can prove this result by induction.
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})$ .

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

Thread: number theory

LinkBack

Thread Tools

Display

number theory

Similar Math Help Forum Discussions

Textbooks on Galois Theory and Algebraic Number Theory

Number Theory

Number Theory

Number Theory type of problem--need help understanding number relationships. yikes.

Number theory, prime number

Search Tags