Results 1 to 2 of 2

Thread: help with short proof

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    14

    help with short proof

    PROBLEM: Let p be a prime an let k be a positive divisor of p-1. Show that the congruence

    x^k≡1 (mod p)

    has exactly k solutions (mod p).

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Let $\displaystyle \alpha$ be a primitive root, and let $\displaystyle \beta = \alpha^{\frac{p-1}{k}}$. Then $\displaystyle 1^k = \beta^k \equiv (\beta^2)^k = \dots = (\beta^{k-1})^k$. (It's easy to see that all of $\displaystyle 1, \beta, \beta^2,\dots, \beta^{k-1}$ are distinct, so we have $\displaystyle k$ solutions.) Moreover if $\displaystyle x$ is a solution, we can write $\displaystyle x=\alpha^y$ for some least nonnegative integer $\displaystyle y$; and then since $\displaystyle \alpha^{yk}=1$ we must have $\displaystyle p-1 \mid yk \Rightarrow yk=m(p-1)$ and then we have that $\displaystyle x=\alpha^{\frac{p-1}{k}m}$ is one of our solutions above.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Short proof ?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 2nd 2011, 02:49 PM
  2. Two short Questions
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: Feb 1st 2010, 04:36 AM
  3. Short Inductive Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 12th 2009, 07:06 PM
  4. Short proof that rows-rank=column-rank?
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Jun 26th 2009, 10:02 AM
  5. short proof
    Posted in the Calculus Forum
    Replies: 8
    Last Post: Sep 24th 2007, 05:40 PM

Search Tags


/mathhelpforum @mathhelpforum