Step in proof of Fermat's little theorem

[Function]

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

[Acme]

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.

[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.

 

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

[Acme]

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

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

[Function]

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...

[Acme]

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?

[John]

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.

[Function]

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!

[Someguy1]

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 May 3, 2014 by Someguy1

[Function]

 

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 May 3, 2014 by Function