## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

MODULAR ARITHMETIC 41
Modular Arithmetic and Solutions of Equations
We can use congruences to prove that some equations have no
integral solutions. For example, suppose we want to show that there
are no integers x and y with the property that x
2
+ y
2
= 11. Suppose
that there were such x and y. Now if two sides of an equation are
equal integers, they are of course congruent modulo any modulus
we like (because their difference is 0, and 0 is divisible by any
positive number.)
So if x
2
+ y
2
= 11, then x
2
+ y
2
11 modulo any number we like.
Let’s choose 4. Then x
2
+ y
2
11 (mod 4). We will now see that this
is impossible. Why?
Consider the squares: they are 0, 1, 4, 9, 16, 25, 36, 49, ... .
Modulo4,theyare0,1,0,1,0,1,0,1,... . (Do you see why there
is such a simple pattern?)
8
So x
2
is either 0 or 1 modulo 4. By the
same token, y
2
is either 0 or 1 modulo 4. Therefore, their sum must
either be 0 + 0 0, 0 + 1 1or1+ 1 2 modulo 4. OK, what’s 11?
It is 3 modulo 4 and so cannot be a sum of two squares.
You might say: “Big deal. To do the original problem, all I needed
to do wa s to test all positive x’s and y’s less than
11, which does
not take long. But now, we can show that there are no integers
x and y with the property that x
2
+ y
2
= 4444444444444411. Our
method works just as before, while your method would take some
time. Also, we get a general theorem: if a 3 (mod 4), then there
arenointegersx and y with the property that x
2
+ y
2
= a.
8
This is because if n is even, so is n
2
, while if n = 2k + 1 is odd, then n
2
= (2k + 1)
2
=
4k
2
+ 4k + 1 leaves a remainder of 1 when divided by 4.

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required