Results 1 to 4 of 4

Thread: need some help on these

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    37
    Awards
    1

    need some help on these

    1) Let p be an odd prime. Prove that there is a primitive root of p
    whose (p-1)th power is NOT congruent to 1 mod p^2.
    Hint: Let g be any primitive root of p. If g works, done.
    If g doesn't work, then show that the primitive root g+p of p
    does work.

    2) For n > 2, let M = 2^n. Prove by induction on n that
    5^(M/8) is congruent to 1 + M/2 mod M.

    3) Show that the solutions to x^e - 1 = 0 mod p in RRS(p)
    are the d numbers b, b^2, ..., b^d mod p, where d=gcd(e,p-1)
    and b is an element mod p of order d.
    Hint: Write d as a linear combination...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by padsinseven View Post
    1) Let p be an odd prime. Prove that there is a primitive root of p
    whose (p-1)th power is NOT congruent to 1 mod p^2.
    Let $\displaystyle a$ be primitive root mod $\displaystyle p$. If $\displaystyle a^{p-1}\equiv 1(\bmod p^2)$ then $\displaystyle (a+p)^{p-1}\equiv a^{p-1} + (p-1)a^{p-2}p\equiv 1 + (p-1)a^{p-2}p\not \equiv 1(\bmod p^2)$.
    But $\displaystyle a+p$ is primitive root mod $\displaystyle p$ also.
    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 padsinseven View Post
    2) For n > 2, let M = 2^n. Prove by induction on n that
    5^(M/8) is congruent to 1 + M/2 mod M.
    I know what you are trying to get at, I just do not like how you wrote it. Here is a redone version which looks nicer.

    Prove: $\displaystyle 5^{2^{k-3}}\equiv 1 + 2^{k-1} (\bmod 2^k)$ for $\displaystyle k\geq 3$.

    Of course $\displaystyle k=3$ is true by so we argue by induction.
    Say $\displaystyle 5^{2^{k-3}}\equiv 1 + 2^{k-1}$ then $\displaystyle \left( 5^{2^{k-3}} \right)^2 \equiv \left( 1 + 2^{k-1} \right)^2 (\bmod 2^{k+1})$.
    Thus, $\displaystyle 5^{2^{k-2}}\equiv 1 + 2^k + 2^{2k-2} \equiv 1 + 2^k(\bmod 2^{k+1})$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by padsinseven View Post
    3) Show that the solutions to x^e - 1 = 0 mod p in RRS(p)
    are the d numbers b, b^2, ..., b^d mod p, where d=gcd(e,p-1)
    and b is an element mod p of order d.
    Let $\displaystyle a$ be primitive root of $\displaystyle p$ (assuming it is odd). Say $\displaystyle x$ solves $\displaystyle x^e = 1(\bmod p)$. Then $\displaystyle x\equiv a^y$ and so $\displaystyle a^{ey}\equiv 1(\bmod p)$ this means $\displaystyle ey\equiv 0(\bmod p-1)$. There are $\displaystyle d=\gcd(e,p-1)$ solutions for $\displaystyle y$. This tells us that $\displaystyle x^e\equiv 1(\bmod p)$ has at most $\displaystyle d$ solutions. It is easy to check that $\displaystyle b,b^2,...,b^d$ are all distinct and each solves $\displaystyle x^e\equiv 1(\bmod p)$. Using the above result that there are at most $\displaystyle d$ solutions it tells us that $\displaystyle b,b^2,...,b^d$ is a complete set of solutions (up to congruence).
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum