Results 1 to 2 of 2

Math Help - 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 \alpha be a primitive root, and let \beta = \alpha^{\frac{p-1}{k}}. Then 1^k = \beta^k \equiv (\beta^2)^k = \dots = (\beta^{k-1})^k. (It's easy to see that all of 1, \beta, \beta^2,\dots, \beta^{k-1} are distinct, so we have k solutions.) Moreover if x is a solution, we can write x=\alpha^y for some least nonnegative integer y; and then since \alpha^{yk}=1 we must have p-1 \mid yk \Rightarrow yk=m(p-1) and then we have that 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: March 2nd 2011, 03:49 PM
  2. Two short Questions
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: February 1st 2010, 05:36 AM
  3. Short Inductive Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 12th 2009, 08:06 PM
  4. Short proof that rows-rank=column-rank?
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: June 26th 2009, 11:02 AM
  5. short proof
    Posted in the Calculus Forum
    Replies: 8
    Last Post: September 24th 2007, 06:40 PM

Search Tags


/mathhelpforum @mathhelpforum