See also the version of this post on Blogger at https://explaining-maths.blogspot.com/2021/07/squares-and-fourth-powers-modulo-k.html where the maths (using MathJax) looks a bit clearer.
Here is another post from my Autumn 2020 introductory pure maths module’s Piazza Forum, continuing the discussion of squares and other powers in modular arithmetic. This has quite a lot in common with my post on squares modulo .
Workshop 7, questions 2 and 3
Hi everyone,
I’ve been asked to explain Workshop 7, questions 2 and 3 a bit further.
There is quite a lot in common here with the previous question on squares modulo .
Here are the questions:
Let’s start with question 2. Rather than repeating the annotations from the Workshop, let’s look at a table similar to the one used in my post on squares modulo . Again this table is larger than needed, but shows the usual repeating patterns we expect to see.
In fact, for similar reasons to those in my post on squares modulo , because the powers we are considering are even powers ( and ), you only really need to check the squares and fourth powers of , and modulo . The rest are repeats modulo . Because:
(i) every integer is congruent to one of , , , or modulo , so we only need to check squares and fourth powers of those numbers modulo ;
(ii) , modulo , so even powers of and don’t give us anything new either.
(See my post on squares modulo for further discussion.)
The conclusions?
(a) , and are squares modulo and and are not squares modulo .
(b) and are fourth powers modulo ; , and are not fourth powers modulo .
In fact, the shortage of fourth powers modulo is not a fluke. This happens modulo when raising integers to the power whenever is prime, by a result known as Fermat’s Little Theorem.
Armed with this, we can look at Question 3.
Now the full solution to Question 3 is in the annotated slides from the workshop, so again it might be good to say something a bit different. But, as mentioned in the annotations, this proof is really an example of Fermat’s method of descent (or “proof by infinite descent”). See https://en.wikipedia.org/wiki/Proof_by_infinite_descent for more details and more examples, including yet another way to show that is irrational!
So, let’s have another look at the equation in question, and call it equation (1).
(1 )
Here we are looking for solutions , , which are integers. Obviously is a solution here. Let’s call this the trivial solution. This question is about showing that the trivial solution is the only solution to equation (1) (with integers , and ).
The “method of descent” proof here is based on showing that, whenever you find a solution with integers , , , then all three of these integers must be divisible by , and , , also solve the same equation. But then the same argument applies to these new integers, and then (by induction) for all natural numbers , , and will also be integers satisfying equation (1). In particular, these are all integers, which somehow looks unlikely for large . Of course this can happen if , but not otherwise. So the only solution is the trivial solution (with integers , and ).
This just leaves the problem of showing that, if integers , and satisfy (1), then they are all divisible by .
To make life a bit simpler, we note that the LHS of (1) is congruent to modulo (since modulo 5).
By question 2, and are congruent to or modulo , so can only be congruent to , or modulo . Moreover, the only way for the LHS to be congruent to modulo is if both and are congruent to modulo , and (since is prime) this happens if and only if and are both divisible by .
Now the RHS of (1) is . This is congruent to or modulo (by question 2 again), and is congruent to modulo if and only if is divisible by . (There are various ways to show the “only if”: for example, if is not divisible by , then must be congruent to modulo 5.)
Now (1) says LHS=RHS, and so, in particular, LHS is congruent to RHS modulo .
But LHS can only be congruent to , or and RHS can only be congruent to or (all modulo ).
So if LHS is congruent to RHS modulo , we must have that both are congruent to modulo .
(No other combination works! Neither of or is congruent to modulo .)
As noted above, this can only happen when all three of , and are divisible by , and that is what we wanted to show.
Best wishes,
Dr Feinstein