Raji, Exercises 3

Raji, Exercises 3.4:

1. Find an integer that gives a remainder of 2 when divided by either 3 or 5, but that is divisible by 4.

Here N = n1n2n3 = 3 4 5 = 60. So N1 = N=3 = 20, N2 = N=4 = 15, and N3 = N=5 = 12. The general technique of Theorem 27 is to ...nd numbers y1, y2, and y3 so that Niyi 1 (mod ni), that is,

20y1

1 (mod 3)

15y2

1 (mod 4)

12y3

1 (mod 5)

These equations are the same as

2y1

1 (mod 3)

3y2

1 (mod 4)

2y3

1 (mod 5)

so we can take y1 = 2, and y2 = 3, and y3 = 3. Or we could take y1 = 1, and y2 = 1, and y3 = 3. Having found y1, y2, and y3, wPe can solve any system of congruences x bi (mod ni) by taking x = Niyibi =

20b1 15b2 + 36b3. In our case, b1 = b3 = 2 and b2 = 0, so we can take x = 40 + 72 = 32.

2. Find all integers that leave a remainder of 4 when divided by 11, and leave a remainder of 3 when divided by 17.

Here N = n1n2 = 11 17, so N1 = N=11 = 17 and N2 = N=17 = 11. We want to ...nd numbers y1 and y2 such that Niyi 1 (mod ni), that is

17y1

1 (mod 11)

11y2

1 (mod 17)

The ...rst equation can be written as 6y1 1 (mod 11) because 6 17 (mod 11). So we want 6y1 = 1 + 11m. One way to do this is just try various values of m until 1 + 11m is divisible by 6. For m = 0 we have 1 + 11m = 1, for m = 1 we have 1 + 11m = 12-- bingo! So we can take y1 = 12=6 = 2. For the second equation we look at the sequence of numbers 1, 18, 35, 52, 69, 86, 103, 120, 137, 154-- bingo! So we could take y2 = 154=11 = 14. That was a bit tedious. Probably better to take y2 = 3. Now we set x = N1y14 + N2y23 = 17 2 4 11 3 3 = 37. Does that work? Yes! But we want all integers, not just one. They are all congruent modulo 11 17 = 187, so the general solution is 37 + 187m.

We can avoid the trial and error in ...nding y1 and y2 by solving Bezout's

1

equation 11s + 17t = 1. The Blankinship table is

11s + 17t s t 17 0 1 11 1 0 611 521 132

so s = 3 and t = 2. Because 11s + 17t = 1, we have the congruences

11s

1 (mod 17)

17t

1 (mod 11)

so we can set y1 = 2 and y2 = 3.

3. Find all integers that leave a remainder of 1 when divided by 2, a remainder of 2 when divided by 3, and a remainder of 3 when divided by 5.

Here N = n1n2n3 = 2 3 5 = 30. So N1 = N=2 = 15, N2 = N=3 = 10, and N3 = N=5 = 6. We want to ...nd y1, y2, and y3 so that Niyi 1 (mod ni), that is

15y1

1 (mod 2)

10y2

1 (mod 3)

6y3

1 (mod 5)

which wePcan easily do by taking y1 = y2 = y3 = 1. As bi = i, we can take x = Niyibi = 15 1 + 10 2 + 6 3 = 53. That clearly works. If we want a smaller number, we could take 23 because 23 53 (mod 30). The general solution is 23 + 30m.

Raji, Exercises 3.5:

1. Show that 10! + 1 is divisible by 11.

Does he want us to compute 10! + 1 = 3628 801 = 329 891 11? Or does he wants us to apply Wilson's theorem which says that, because 11 is a prime, it divides (11 1)! + 1? I would guess the latter.

2. What is the remainder when 5!25! is divided by 31? Here I'm quite sure he doesn't want the computation

5!25! = 1861 345 205 199 718 318 080 000 000

so what can we do? We know that 30! 1 (mod 31). Can we relate 5!25! to 30!? Well 30 1 (mod 31), and 29 2 (mod 31), and so on, so 30 29 28 27 26 ( 1) ( 2) ( 3) ( 4) ( 5) (5!) (mod 31). But

30! = (30 29 28 27 26) (25!)

so 30! (5!25!) (mod 31). So 5!25! 1 (mod 31).

2

3. What is the remainder when 5100 is divided by 7? We've done these before, but now we know Fermat's theorem which says that 56 1 (mod 7). So 5100 = 56 16+4 = 56 16 54 54 (mod 7). We still have to compute 54 mod 7 by hand. The ...rst four powers of 5 modulo 7 are 5; 4; 6; 2, so the answer is 2.

4. Show that if p is an odd prime, then 2 (p 3)! 1 (mod p). This is like Exercise 2, only easier. We have p 1 1 (mod p) and p 2 2 (mod p), so (p 1)! ( 1) ( 2) (p 3)! (mod p). The result then follows from Wilson's theorem. Where did we use the fact that p was odd? Is the statement true for p = 3?

3

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download