Results 1 to 3 of 3

Thread: 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 $\displaystyle p^k $, then r is a primitive root of $\displaystyle p^i$ , $\displaystyle 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 $\displaystyle r^n\equiv a(modp)$ iff $\displaystyle 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 $\displaystyle \phi(p)/gcd(\phi(p),inda)$

    4) show that if $\displaystyle a^k\equiv1(modp) $,$\displaystyle a^h\equiv1(modp)$ ,then $\displaystyle 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 $\displaystyle p^k $, then r is a primitive root of $\displaystyle p^i$ , $\displaystyle 1<i<k$

    [hint: use induction of i ]
    To prove this we need to use the following fact: if $\displaystyle a\equiv b (\bmod p^n)$ for $\displaystyle n\geq 1$ then $\displaystyle a^p \equiv b^p (\bmod p^{n+1} )$. To prove this we write $\displaystyle a = b + c\cdot p^n$ and so $\displaystyle a^p = (b+c\cdot p^n)^p = b^p + d\cdot p^{n+1}$ where $\displaystyle d$ is everything in between the binomial expansion, here we are using a well-known fact that $\displaystyle p$ divides the innermost binomial coefficients, but because of the presence of $\displaystyle p^n$ it means that the innermost binomial coefficients are all divisible by $\displaystyle p^n$ too, and so everything in the middle is divisible by $\displaystyle p^{n+1}$, thus, $\displaystyle a^p \equiv b^p (\bmod p^{n+1})$. Now we have the tool to prove what you wish to show. Suppose $\displaystyle r $ is a primitive root of $\displaystyle p^k$, $\displaystyle k\geq 1$. This means the order of $\displaystyle r$ is $\displaystyle \phi (p^k) = p^k - p^{k-1}$. Now we claim that $\displaystyle r$ is a primitive root of $\displaystyle p^{k-1}$ too, this means we have to show the order of $\displaystyle r$ mod $\displaystyle p^{k-1}$ is $\displaystyle \phi (p^{k-1}) = p^{k-1} - p^{k-2}$. Suppose it is not a primitive root with order $\displaystyle m < p^{k-1} - p^{k-2}$ then $\displaystyle r^m \equiv 1 (\bmod p^{k-1})$ using the above result it means $\displaystyle r^{mp} \equiv 1 (\bmod p^k )$ but $\displaystyle mp < (p^{k-1} - p^{k-2})p = p^k - p^{k-1} = \phi (p^k)$, and so it contradicts the fact that $\displaystyle r$ is a primitive root of $\displaystyle p^k$. Now we can prove that $\displaystyle r$ is a primitive root of $\displaystyle p^{k-2}$, i.e. the order is $\displaystyle \phi (p^{k-2}) = p^{k-2} - p^{k-3}$, suppose the order of $\displaystyle r$ was $\displaystyle m < p^{k-2} - p^{k-3}$ then $\displaystyle r^m \equiv 1 (\bmod p^{k-2})$ and that means $\displaystyle r^{mp} \equiv 1 (\bmod p^{k-1})$ but then $\displaystyle 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 $\displaystyle 1\leq i\leq k$ we have that $\displaystyle r$ is primitive root of $\displaystyle 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 $\displaystyle r^n\equiv a(modp)$ iff $\displaystyle 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 $\displaystyle \phi(p)/gcd(\phi(p),inda)$
    Let us make a more general proof. Let $\displaystyle n\geq 2$ be a positive integer that has a primitive root $\displaystyle r$. Let $\displaystyle a$ be an integer such that $\displaystyle \gcd (a,n) = 1$. Then if $\displaystyle k = \mbox{ord}(a)$ it means $\displaystyle k$ is the least positive exponent such that $\displaystyle a^k \equiv 1 (\bmod n)$. Now is $\displaystyle s = \mbox{ind}(a)$ then it means $\displaystyle a \equiv r^s (\bmod n)$ and so $\displaystyle a^k \equiv 1 \implies (r^s)^k \equiv 1 (\bmod n )$. Thus, we are looking for the order of $\displaystyle r^s$ which is $\displaystyle \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: Dec 28th 2009, 10:26 PM
  2. Roots & Imaginary Roots
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: Oct 4th 2009, 09:24 AM
  3. Funtions and Primitives
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Jul 7th 2009, 06:11 AM
  4. Given 2 imaginary roots find other 2 roots
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Jan 26th 2008, 09:24 PM
  5. Primitives , check My results please
    Posted in the Calculus Forum
    Replies: 13
    Last Post: Nov 20th 2007, 08:52 AM

Search Tags


/mathhelpforum @mathhelpforum