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

  • Thread starter SpiffyEh
  • Start date
  • #1
194
0

Homework Statement


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.


Homework Equations


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



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?
 

Answers and Replies

  • #2
194
0
Can anyone help with this? I really need to understand how it works
 
  • #3
473
13
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.
 

Related Threads on Proving X^(k*p-1)+1)mod p = x mod p

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
13K
Top