Results 1 to 4 of 4

Math Help - 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
    9
    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 a be primitive root mod p. If a^{p-1}\equiv 1(\bmod p^2) then (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 a+p is primitive root mod 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
    9
    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: 5^{2^{k-3}}\equiv 1 + 2^{k-1} (\bmod 2^k) for k\geq 3.

    Of course k=3 is true by so we argue by induction.
    Say 5^{2^{k-3}}\equiv 1 + 2^{k-1} then \left( 5^{2^{k-3}} \right)^2 \equiv \left( 1 + 2^{k-1} \right)^2 (\bmod 2^{k+1}).
    Thus, 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
    9
    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 a be primitive root of p (assuming it is odd). Say x solves x^e = 1(\bmod p). Then x\equiv a^y and so a^{ey}\equiv 1(\bmod p) this means ey\equiv 0(\bmod p-1). There are d=\gcd(e,p-1) solutions for y. This tells us that x^e\equiv 1(\bmod p) has at most d solutions. It is easy to check that b,b^2,...,b^d are all distinct and each solves x^e\equiv 1(\bmod p). Using the above result that there are at most d solutions it tells us that b,b^2,...,b^d is a complete set of solutions (up to congruence).
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum