# Step in proof of Fermat's little theorem

## Recommended Posts

hello everyone

Let me get straight to the point:

$p$ is prime, $a\in\mathbb{N}$, $p\nmid a$;

$A=\{a,2a,3a,\cdots ,(p-1)a\}$

Let $ra\equiv sa\pmod{p}$

Then: $ra=mp+R$ and $sa=np+R$

$(r-s)a=(m-n)p$

So $p\mid (r-s)$

So $r\equiv s\pmod{p}$

The elements of $A$ must thus all be different and congruent with the elements of the set $B=\{1,2,3,\cdots ,(p-1)\}$. 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

##### Share on other sites

hello everyone

Let me get straight to the point:

$p$ is prime, $a\in\mathbb{N}$, $p\nmid a$;

$A=\{a,2a,3a,\cdots ,(p-1)a\}$

Let $ra\equiv sa\pmod{p}$

Then: $ra=mp+R$ and $sa=np+R$

$(r-s)a=(m-n)p$

So $p\mid (r-s)$

So $r\equiv s\pmod{p}$

The elements of $A$ must thus all be different and congruent with the elements of the set $B=\{1,2,3,\cdots ,(p-1)\}$. 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.

##### 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?

##### Share on other sites

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.

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

##### 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?

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

##### 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!

##### Share on other sites

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

p is prime, $a\in\mathbb{N}, p\nmid a$
Let $A=\{a,2a,3a,\cdots ,(p-1)a\}$
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 $ra\equiv sa\pmod{p}$ with $1 \leq r, s \leq p-1$
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 $ra\equiv sa\pmod{p}$ then
$p |(ra - sa) = (r - s) a$
Then you can apply the theorem that $p \mid ab$ implies that either $p \mid a$ or $p \mid b$, plus the fact that $p \nmid a$ to conclude that
$p | (r - s)$
So $r\equiv s\pmod{p}$
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 $B=\{1,2,3,\cdots ,(p-1)\}$. The sequence is not important.
And now tell us the rest Edited by Someguy1
##### Share on other sites

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

p is prime, $a\in\mathbb{N}, p\nmid a$
Let $A=\{a,2a,3a,\cdots ,(p-1)a\}$
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 $ra\equiv sa\pmod{p}$ with $1 \leq r, s \leq p-1$
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 $ra\equiv sa\pmod{p}$ then
$p |(ra - sa) = (r - s) a$
Then you can apply the theorem that $p \mid ab$ implies that either $p \mid a$ or $p \mid b$, plus the fact that $p \nmid a$ to conclude that
$p | (r - s)$
So $r\equiv s\pmod{p}$
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 $B=\{1,2,3,\cdots ,(p-1)\}$. 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

## Create an account

Register a new account