Proof of Little Fermat's Theorem for a=7

85 Views Asked by At

In the book I read there are proofs of FLT for certain cases before the common case.

When a=7, authors first write that it's possible to check all remainders of $a\mod7$, and then that it's ineffective and that $(a^7-7)\mod7$ can be represented as multiplication of seven consequent numbers (by module 7).

But before that they write something like:

As soon as every integer can be represented as $a-7b,7b \pm1,7b\pm2,7b\pm3$ it's obvious that we can check only $a=0,1,2,3 \mod 7 $

Why is it obvious?

2

There are 2 best solutions below

0
On BEST ANSWER

I guess the idea is that $(-a)^7\equiv -(a^7) \pmod{7}$, and if you already know that $a^7\equiv a\pmod{7}$, then this gives $(-a)^7\equiv -(a^7)\equiv -a\pmod{7}$.

Once you've checked this works for $a=0,1,2,3$, the other values are negatives of these values, and so the above applies.

Honestly, maybe it would've been easier just to check the other three cases. :-)

0
On

When you write $n=7a+r$, then $$ n^7=(7a+r)^7=A+r^7 $$ where $A$ represents all terms in the binomial expansion that contain a power of the first summand (that is, a power of $7a$). Then $A$ is divisible by $7$ and only $r^7$ is significant for determining the remainder of $n^7$ when divided by $7$.

Next, $(-b)^7=-b^7$. Thus if you check the property when the remainder is $3$, you already have the check when the remainder is $-3$ (and the same for $0$, $1$ and $2$, of course).

However, this is too long and too little general. The important things to remember are the properties of congruences:

if $A\equiv B\pmod{N}$ and $C\equiv D\pmod{N}$, then $$(A+C)\equiv(B+D)\pmod{N}\qquad\text{and}\qquad AC\equiv BD\pmod{N}$$

In particular, if $n\equiv b\pmod{7}$, then $n^7\equiv b^7\pmod{7}$.