1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proving X^(k*p-1)+1)mod p = x mod p

  1. Jan 29, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove that x^(k(p–1)+1) mod p = x mod p for all primes p and integer k ≥ 0.
    Hint: Use Fermat’s Little theorem and induction on k.

    2. Relevant equations
    I understand that fermat's little theorm is:
    Let p be prime, and b e Z_p. Then b^p = b (mod p).

    3. The attempt at a solution
    Proof given in class:

    If x is 0 mod p, then the statement is trivially true, so assume gcd(x,p) = 1

    Let k = 1. We need to establish that x^(1(p–1)+1) = x mod p
    Left side = x^p, and this = p mod p by FLT.

    Now assume true for a given k, so that x^(k(p–1)+1) = x mod p
    A variant of FLT tells you that x^(p–1) = 1 mod p when gcd(x,p) = 1, so apply that to
    x^(k(p–1)+1) = x mod p

    x^(k(p–1)+1) times x^(p-1) = x times 1 mod p
    x^((k+1)(p–1)+1) = x mod p

    I don't understand how this proves it at all. To me it just seems to get more complex at the end. Can anyone explain to me how this works?
  2. jcsd
  3. Jan 30, 2012 #2
    Can anyone help with this? I really need to understand how it works
  4. Jan 31, 2012 #3
    It sounds like you don't really understand induction. The basic idea is that you prove two things, for some statement S depending on a number:
    • S(1) is true
    • If S(k) is true, so is S(k+1).
    And then this is taken - by induction - to prove that S(n) is true for all n, the truth "inheriting" through to all numbers.

    The alternative statement of Fermat's Little Theorem in the middle of the proof there, that [itex] a^{p-1}\equiv1 \text{ mod }p[/itex], can be used to eliminate the need for induction. Then it's just a matter of knowing that 1k=1 for all k.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook