Jump to content

Step in proof of Fermat's little theorem


Function
 Share

Recommended Posts

hello everyone

 

Let me get straight to the point:

 

[math]p[/math] is prime, [math]a\in\mathbb{N}[/math], [math]p\nmid a[/math];

 

[math]A=\{a,2a,3a,\cdots ,(p-1)a\}[/math]

 

Let [math]ra\equiv sa\pmod{p}[/math]

 

Then: [math]ra=mp+R[/math] and [math]sa=np+R[/math]

 

[math](r-s)a=(m-n)p[/math]

 

So [math]p\mid (r-s)[/math]

 

So [math]r\equiv s\pmod{p}[/math]

 

The elements of [math]A[/math] must thus all be different and congruent with the elements of the set [math]B=\{1,2,3,\cdots ,(p-1)\}[/math]. The sequence is not important.

 

I found these steps of the proof (which continues after this) on the internet, and I don't really get the statement I put bold...

 

Can someone explain this to me? Thanks!

 

Function

Link to comment
Share on other sites

hello everyone

 

Let me get straight to the point:

 

[math]p[/math] is prime, [math]a\in\mathbb{N}[/math], [math]p\nmid a[/math];

 

[math]A=\{a,2a,3a,\cdots ,(p-1)a\}[/math]

 

Let [math]ra\equiv sa\pmod{p}[/math]

 

Then: [math]ra=mp+R[/math] and [math]sa=np+R[/math]

 

[math](r-s)a=(m-n)p[/math]

 

So [math]p\mid (r-s)[/math]

 

So [math]r\equiv s\pmod{p}[/math]

 

The elements of [math]A[/math] must thus all be different and congruent with the elements of the set [math]B=\{1,2,3,\cdots ,(p-1)\}[/math]. The sequence is not important.

 

I found these steps of the proof (which continues after this) on the internet, and I don't really get the statement I put bold...

 

Can someone explain this to me? Thanks!

 

Function

Off the cuff I think it just means that it doesn't matter in what order you choose test cases. For example, you could let p=7 and let a=2 first, even though 7 is not the first prime and 2 is not the first a.

Link to comment
Share on other sites

Off the cuff I think it just means that it doesn't matter in what order you choose test cases. For example, you could let p=7 and let a=2 first, even though 7 is not the first prime and 2 is not the first a.

 

what about the congruency of elements of A to those of B?

Link to comment
Share on other sites

It's awkward wording, but I think B just shows that the a's are Natural numbers.

 

In an explanation of the proof, it says: division of elements of A and division of elements of B by p, will result in equal remainders...

Link to comment
Share on other sites

In an explanation of the proof, it says: division of elements of A and division of elements of B by p, will result in equal remainders...

Hmmmmmm...while we wait to see if others respond, can you link to the page you are reading from?

Link to comment
Share on other sites

It may just be noting that, given our a and p, the first p - 1 positive multiples of a will, mod p, give us the first p - 1 natural numbers, though not necessarily in order.

 

As an example, consider a = 8 and p = 5. Then the first p - 1 = 4 multiples of a are 8, 16, 24 and 32. These are congruent (mod 5) to 3, 1, 4 and 2, respectively.

Link to comment
Share on other sites

It may just be noting that, given our a and p, the first p - 1 positive multiples of a will, mod p, give us the first p - 1 natural numbers, though not necessarily in order.

 

As an example, consider a = 8 and p = 5. Then the first p - 1 = 4 multiples of a are 8, 16, 24 and 32. These are congruent (mod 5) to 3, 1, 4 and 2, respectively.

 

Now that, seems very plausible. Thanks, John!

Link to comment
Share on other sites

Let's unpack this a little by annotating as we go.

 

p is prime, [latex]a\in\mathbb{N}, p\nmid a[/latex]
Let [latex]A=\{a,2a,3a,\cdots ,(p-1)a\}[/latex]
Now, we want to show that these p-1 numbers in A are all the nonzero residues mod p. In other words, no two of these are equal mod p. So, assume that two of them are equal.
Let [latex]ra\equiv sa\pmod{p}[/latex] with [latex] 1 \leq r, s \leq p-1[/latex]
Then: ra=mp+R and sa=np+R
What is R? This is a little messy. I think I would just skip that line entirely since there's an easier way to go. Note that if [latex]ra\equiv sa\pmod{p}[/latex] then
[latex]p |(ra - sa) = (r - s) a[/latex]
Then you can apply the theorem that [latex]p \mid ab[/latex] implies that either [latex]p \mid a[/latex] or [latex]p \mid b[/latex], plus the fact that [latex]p \nmid a[/latex] to conclude that
[latex]p | (r - s)[/latex]
So [latex]r\equiv s\pmod{p}[/latex]
But r and s are between 1 and p - 1, so the only way they can be equivalent mod p is if r = s. In other words, the set A contains a complete set of nonzero residues mod p in some order. That's what they mean by:
The elements of A must thus all be different and congruent with the elements of the set [latex]B=\{1,2,3,\cdots ,(p-1)\}[/latex]. The sequence is not important.
And now tell us the rest :)
Edited by Someguy1
Link to comment
Share on other sites

 

Let's unpack this a little by annotating as we go.

 

p is prime, [latex]a\in\mathbb{N}, p\nmid a[/latex]
Let [latex]A=\{a,2a,3a,\cdots ,(p-1)a\}[/latex]
Now, we want to show that these p-1 numbers in A are all the nonzero residues mod p. In other words, no two of these are equal mod p. So, assume that two of them are equal.
Let [latex]ra\equiv sa\pmod{p}[/latex] with [latex] 1 \leq r, s \leq p-1[/latex]
Then: ra=mp+R and sa=np+R
What is R? This is a little messy. I think I would just skip that line entirely since there's an easier way to go. Note that if [latex]ra\equiv sa\pmod{p}[/latex] then
[latex]p |(ra - sa) = (r - s) a[/latex]
Then you can apply the theorem that [latex]p \mid ab[/latex] implies that either [latex]p \mid a[/latex] or [latex]p \mid b[/latex], plus the fact that [latex]p \nmid a[/latex] to conclude that
[latex]p | (r - s)[/latex]
So [latex]r\equiv s\pmod{p}[/latex]
But r and s are between 1 and p - 1, so the only way they can be equivalent mod p is if r = s. In other words, the set A contains a complete set of nonzero residues mod p in some order. That's what they mean by:
The elements of A must thus all be different and congruent with the elements of the set [latex]B=\{1,2,3,\cdots ,(p-1)\}[/latex]. The sequence is not important.
And now tell us the rest :)

 

 

R is the remainder.

 

I get everything until you get to "In other words, the set A ..."

Why is this? I do see that if both r and s are between 1 and p-1, they can only be equivalent modulo p if they're equal... But what does this prove?

Only thing it shows, as I see it, is that all the elements of A are different from each other; but this was kinda logic? I mean, if this is the reason of that step, to show that the elements of A are different... Why? Isn't it just logic that a isn't equal to 2a, to 3a and so on?

 

EDIT: I see what you're doing, and I get it.. So you're showing that ra and sa can only be equivalent mod p, if and only if r and s are equal? But why not just say that a isn't equal to 2a? and so on?

 

RE-EDIT: oh no wait, I think I get it. Thanks!

 

The rest of the proof is rather easy:

 

Since the elements of A and B are, in some order, equivalent modulo p, the product of all elements of A should be equivalent modulo p with the products of all elements of B.

 

Work it out, and you get Fermat's little theorem

Edited by Function
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.