Results 1 to 3 of 3

Math Help - proplems in primitives roots

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    12

    proplems in primitives roots

    please i need help in foloowing propems

    1) if r is primitive root of p^k , then r is a primitive root of p^i , 1<i<k

    [hint: use induction of i ]


    2) le t be a prime , r be any primitive root of p , let a be any positive integer with gcd(a,p)=1 , then ; prove that r^n\equiv a(modp) iff a\equiv ind a(mod p^-1)


    3) let p be prime , r any primitive root of p , let a be any (+ve) integer such that gcd(a,p)=1 then prove that the order of a modoulo p is \phi(p)/gcd(\phi(p),inda)

    4) show that if a^k\equiv1(modp) ,  a^h\equiv1(modp) ,then a^hp\equiv 1(modp^2)
    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 midosoft View Post
    please i need help in foloowing propems
    1) if r is primitive root of p^k , then r is a primitive root of p^i , 1<i<k

    [hint: use induction of i ]
    To prove this we need to use the following fact: if a\equiv b (\bmod p^n) for n\geq 1 then a^p \equiv b^p (\bmod p^{n+1} ). To prove this we write a = b + c\cdot p^n and so a^p = (b+c\cdot p^n)^p = b^p + d\cdot p^{n+1} where d is everything in between the binomial expansion, here we are using a well-known fact that p divides the innermost binomial coefficients, but because of the presence of p^n it means that the innermost binomial coefficients are all divisible by p^n too, and so everything in the middle is divisible by p^{n+1}, thus, a^p \equiv b^p (\bmod p^{n+1}). Now we have the tool to prove what you wish to show. Suppose r is a primitive root of p^k, k\geq 1. This means the order of r is \phi (p^k) = p^k - p^{k-1}. Now we claim that r is a primitive root of p^{k-1} too, this means we have to show the order of r mod p^{k-1} is \phi (p^{k-1}) = p^{k-1} - p^{k-2}. Suppose it is not a primitive root with order m < p^{k-1} - p^{k-2} then r^m \equiv 1 (\bmod p^{k-1}) using the above result it means r^{mp} \equiv 1 (\bmod p^k ) but mp < (p^{k-1} - p^{k-2})p = p^k - p^{k-1} = \phi (p^k), and so it contradicts the fact that r is a primitive root of p^k. Now we can prove that r is a primitive root of p^{k-2}, i.e. the order is \phi (p^{k-2}) = p^{k-2} - p^{k-3}, suppose the order of r was m < p^{k-2} - p^{k-3} then r^m \equiv 1 (\bmod p^{k-2}) and that means r^{mp} \equiv 1 (\bmod p^{k-1}) but then mp < p(p^{k-2} - p^{k-3}) = p^{k-1} - p^{k-2} = \phi (p^{k-1}) which is a contradiction. And now work yourself down by induction. And thus, for 1\leq i\leq k we have that r is primitive root of p^i.
    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 midosoft View Post
    2) le t be a prime , r be any primitive root of p , let a be any positive integer with gcd(a,p)=1 , then ; prove that r^n\equiv a(modp) iff a\equiv ind a(mod p^-1)
    This problem just does not make any sense.

    3) let p be prime , r any primitive root of p , let a be any (+ve) integer such that gcd(a,p)=1 then prove that the order of a modoulo p is \phi(p)/gcd(\phi(p),inda)
    Let us make a more general proof. Let n\geq 2 be a positive integer that has a primitive root r. Let a be an integer such that \gcd (a,n) = 1. Then if k = \mbox{ord}(a) it means k is the least positive exponent such that a^k \equiv 1 (\bmod n). Now is s = \mbox{ind}(a) then it means a \equiv r^s (\bmod n) and so a^k \equiv 1 \implies (r^s)^k \equiv 1 (\bmod n ). Thus, we are looking for the order of r^s which is \phi(n)/\gcd(\phi(n),s) (this is a theorem you should know).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitives of the natural logarithm
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 28th 2009, 11:26 PM
  2. Roots & Imaginary Roots
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: October 4th 2009, 10:24 AM
  3. Funtions and Primitives
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 7th 2009, 07:11 AM
  4. Given 2 imaginary roots find other 2 roots
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: January 26th 2008, 10:24 PM
  5. Primitives , check My results please
    Posted in the Calculus Forum
    Replies: 13
    Last Post: November 20th 2007, 09:52 AM

Search Tags


/mathhelpforum @mathhelpforum