Results 1 to 3 of 3

Thread: number theory

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    39

    number theory

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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}^ +
    $
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by felixmcgrady View Post
    2. let n= 3^(t-1). show that 2^n = -1 (mod 3^t)
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Jul 8th 2011, 06:09 PM
  2. Number Theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 19th 2010, 07:51 PM
  3. Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Feb 16th 2010, 05:05 PM
  4. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum