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.

Start Free Trial

No credit card required