18.

781 Homework 1

Due: 9th February 2014

Q 1 (1.2(6)). Prove that the product of three consecutive integers is divisible by 6; of four consecutive integers
by 24.

Proof. Let the integers be n, n + 1 and n + 2. If n is odd, then n = 2k + 1 for some integer k by the
division algorithm the product n(n + 1)(n + 2) = 2(2k + 1)(k + 1)(2k + 3) is even. If n is even, say n = 2k,
then the product n(n + 1)(n + 2) = 2k(2k + 1)(2k + 2) is even. If 3 divides n, then 3 divides the product
n(n + 1)(n + 2). If 3 does not divide n, then either n = 3k + 1 for some integer k or n = 3l + 2 for some
integer l by the division algorithm. In the first case, n + 2 = 3k + 3 = 3(k + 1) is divisible by 3 and therefore
so is n(n + 1)(n + 2) and in the second case n + 1 = 3k + 3 = 3(k + 1) is divisible by 3 and therefore so is
the product n(n + 1)(n + 2). n(n + 1)(n + 2) = 3m for some integer m and 2 divides 3m. As (2, 3) = 1,
Theorem 1.10 tells us 2 | m, say m = 2l for some integer l, then n(n + 1)(n + 2) = 3(2l) = 6l. This shows
the product is divisible by 6.
As the product of three consecutive integers is divisible by 3, so is the product of four consecutive
integers. Again let the first of the four integers be n. If n is divisible by 4, then n = 4k for some integer k
and n(n+2) = 4k(4k +2) = 8k(2k +1) is divisible by 8 and therefore so is the product of the four consecutive
integers starting with 4. if n = 4k + 1, then (n + 1)(n + 3) = (4k + 2)(4k + 4) = 8(k + 1)(k + 1) is divisible
by 4 and therefore so is n(n + 1)(n + 2)(n + 3). Similarly, if n = 4k + 2, then n(n + 2) is divisible by 8 and
if n = 4k + 3, (n + 1)(n + 3) is divisible by 8, so the product n(n + 1)(n + 2)(n + 3) in all cases is divisible
by 8. Let the product equal 8l for some integer l. As 3 divides 8l and (3, 8) = 1, l = 3m for some integer m
and the product equals 8(3m) = 24m. So 24 divides the product of four consecutive integers.

Q 2 (1.2(9)). Show that if c 6= 0 and ac | bc then a | b .

Proof. ac | bc implies that there exists an integer k such that ack = bc but this implies c(ak − b) = 0. As
c 6= 0, ak − b = 0 which implies a | b.
Q 3 (1.2(11)). Prove that 4 - (n2 + 2) for any integer n.

Proof. If n is even, that is n = 2k for some integer k, then n2 + 2 = 4k 2 + 2, which shows that n2 + 2 divided
by 4 leaves a remainder of 2 (as k 2 ≥ 0), so 4 - n2 + 2. If n is odd, then n = 2k + 1 for some integer k and
n2 + 2 = 4(k 2 + k) + 3. If 4 | n2 + 2, then 4 | (n2 + 2) − (4(k 2 + k)) i.e. 4 | 3, which is a contradiction.
Q 4 (1.2(13)). Prove that n2 − n is divisible by 2 for every integer n; that n3 − n is divisible by 6; that n5 − n
is divisible by 30.

Proof. n2 − n = (n − 1)n is the product of two consecutive integers so is divisible by 2 (either n − 1

or n is even). n3 − n = (n − 1)n(n + 1) is the product of three consecutive integers and so is divisible
by 6. n5 − n = n(n2 − 1)(n2 + 1) = (n3 − n)(n2 + 1) so it is divisible by 6. Write n = 5q + r using
the division algorithm. Multiplying 5q + r with itself 5 times and expanding the product, we see that
(5q + r)5 − (5q + r) = 5k + (r5 − r) for some integer k, so now it suffices to check that 5 divides r5 − r for
r = 0, 1, 2, 3, 4 and this is clear. Let n5 − n = 6m for some integer m. As 5 | 6m and (5, 6) = 1, we see that
5 | m i.e. m = 5l for some integer l and therefore n5 − n = 30l or in other words 30 | n5 − n.
Q 5 (1.2(15)). Prove that if x and y are odd, then x2 + y 2 is even but not divisible by 4.

1
Proof. Write x = 2k + 1 and y = 2l + 1 for some integers k and l. x2 + y 2 = 4(k 2 + l2 + k + l) + 2 =
2(2k 2 + 2l2 + 2k + 2l + 1). This shows x2 + y 2 is even. If 4 | x2 + y 2 , then 4 | (x2 + y 2 ) − 4(k 2 + l2 + k + l) = 2
which is a contradiction. So 4 - x2 + y 2 .
Q 6 (1.2(23)). Prove that the square of any integer is of the form 3k or 3k + 1 but not of the form 3k + 2.

Proof. Let the integer be n. The problem can be restated as saying the division algorithm gives either 0 or
1 as remainder when n2 is divided by 3, and never 2. By the division algorithm, n = 3q + r for r ∈ {0, 1, 2}.
If r = 0, then, n2 = 9q 2 = 3(3q 2 ). If r = 1, then n2 = 3(3q 2 + 2q) + 1. If r = 2, then n2 = 3(3q 2 + 4q + 1) + 1.
As the quotient and remainder when n2 when divided by 3 are uniquely determined, we see that in these
cases the quotient is 3q 2 , 3q 2 + 2q, 3q 2 + 4q + 1 respectively and the remainder is 0 in the first case and 1 in
the other two cases.
Q 7 (1.2(47)). If a and b > 2 are any positive integers, prove that 2a + 1 is not divisible by 2b − 1.
Proof. If b > a, then 2b − 2a = 2a (2(b−a) − 1) > 2 as a > 2, so 2b − 1 > 2a + 1 and so 2a + 1 cannot be
divisible by 2b − 1. If b = a, then the division algorithm in this case gives quotient 1 and remainder 2 (as
2 < 22 − 1 < 2b − 1 as b > 2). If a > b, then, 2a + 1 = (2(a−b) (2b − 1)) + (2(a−b) + 1). So from this we see that
if 2b − 1 divides 2a + 1, then it must also divide 2a + 1 − (2b − 1)(2(a−b) ) = 2(a−b) + 1. We can now repeat the
argument with a − b in place of a. This argument must stop in k steps where (a − kb) ≤ b < (a − (k − 1)b)
as we end up in one of the first two cases.
Q 8 (1.2(2)). Find the greatest common divisor g of the numbers 1819 and 3587 and then find integers x
and y to satisfy 1819x + 3587y = g.

Proof.
3587 = 1.(1819) + 1768
1819 = 1.(1768) + 51
1768 = 34.(51) + 34
51 = 1.(34) + 17
34 = 2.(17)
So the greatest common divisor is 17.

17 = 51 − 34
= 51 − (1768 − 34.(51)) = 35.(51) − 1768
= 35.(1819 − 1768) − 1768 = 35.(1819) − 36.(1768)
= 35.(1819) − 36.(3587 − 1819))
= 71.(1819) − 36.(3587)

x = 71 and y = −36 is one possible answer. There are other possible pairs of solutions, each of them is given
by {x = 71 + 211k, y = −36 − 107k} for some integer k.
Q 9 (1.2(12)). Given that (a, 4) = 2 and (b, 4) = 2, prove that (a + b, 4) = 4.

Proof. Since (a, 4) = 2, 2 divides a and 4 does not, the division algorithm when we divide a by 4 should
leave a remainder of 2 i.e. a = 4k + 2 for some integer k. Similarly, b = 4l + 2 for some integer l. Therefore,
a + b = 4(k + l) + 2 + 2 = 4(k + l + 1). So 4 divides a + b and therefore the greatest common divisor of
a + b and 4 must be 4 (4 is a common divisor and the greatest common divisor cannot be strictly bigger
than either of the numbers).

Q 10 (1.2(26)). Let s and g > 0 be given integers. Prove that integers x and y exist satisfying x + y = s
and (x, y) = g if and only if g | s.

2
Proof. If there exist integers x and y satisfying x + y = s and (x, y) = g, then as x = gx0 and y = gy 0 , so
s = x + y = g(x0 + y 0 ), so g | x. For the other direction, take x = g and y = s − g. Then clearly x + y = s.
Let s = gk for some k. Then,

(x, y) = (g, s − g) = (g, gk − g) = g(1, k − 1) = g

Q 11 (1.2(53)). Show that (n! + 1, (n + 1)! + 1) = 1.

Proof.

(n! + 1, (n + 1)! + 1) = (n! + 1, (n + 1)! + 1 − (n + 1)(n! + 1) = (n! + 1, −n) = (n! + 1, n) = 1

The last equality holds as we can find integers x and y satisfying x(n! + 1) + y(n) = 1 (namely x = 1 and
y = −(n − 1)!), and as the greatest common divisor of the two is the smallest integer which can be written
in this form, we see that it must equal 1.
√
Q 12 (1.3(24)). Prove that if n is composite, it must have a prime factor p ≤ n . (Note that a straight-
forward implication of this problem i s that if we want √ to test whether an integer n is a prime, it suffices to
check whether it is divisible by any of the primes ≤ n . For example, if n = 1999, we check divisibility by
the primes 2, 3, 5, · · · , 43. This is easy to do with a hand calculator. It turns out that 1999 is divisible by
none of these primes, so it is itself a prime.)
√
Proof. Suppose n is composite and every prime factor of n is strictly larger than n. Let n = pm for some
prime p. By assumption m 6= 1 and √ as any prime factor of m is also a prime factor of n, every prime factor
√
of m is also strictly bigger √ √than n. As m is at least as large as any of its prime factors, we have m > n.
So we√have n = pm > n. n = n which is a contradiction. So n must have at least one prime factor less
than n.
Q 13 (1.3(25)). Obtain a complete list of the primes between 1 and n, with n = 200 for convenience, by
the following method, known as the sieve of Eratosthenes. By the proper multiples of k we mean all positive
multiples of k except k itself. Write all numbers from 2 to 200. Cross out all proper multiples of 2, then of 3,
then of 5. At each stage the next larger remaining number is a prime. Thus 7 is now the next remaining iarger
than 5. Cross out the proper multiples of 7. The next remaining number larger than 7 is 1 1. Continuing,
we cross out the proper √multiples of 11 and then of 13. Now we observe that the next remaining number
greater than 13 exceeds 200, and hence by the previous problem all the numbers remaining in our list are
prime.
Proof. At the first stage cross out all even numbers less than or equal to 200 (so that cuts down 100 numbers
out of the 199), next stage cross out all multiples of 3 that are not multiples of 6, so that cuts down another
33 numbers, at the next stage cross out multiples of 7 that are not already multiples of √ 2 or√3 and so on...
Any composite number n less than or equal to 200 must have a prime factor less than n ≤ 200 < 15. So
once we strike off all the multiples less than 200 of all the primes less than 15, the remaining numbers must
be prime, as they have no prime factor less than or equal to their square root.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

Q 14 (1.3(44)). If 2n − 1 is a prime for some integer n, prove that n is itself a prime. (Numbers of
the form 2p − 1, where p is a prime, are called the Mersenne numbers MP because the Frenchman Fa-
ther Marin Mersenne (1588-1648) stated the Mp is a prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257,
but is composite for all other primes p < 257. It took some 300 years before the details of this as-
sertion could be checked completely, with the following outcome: Mp is not a prime for p = 67 and
p = 257, and Mp is a prime for p = 61, p = 89, and p = 107. Thus, there are 12 primes p < 257
such that Mp is a prime. It is now known that Mp is a prime in the following additional cases, p =

3
521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091.
The Mersenne prime M216091 is the largest specific number that is known to be prime. It is conjectured that
infinitely many of the Mersenne numbers are prime.)
Proof. We will prove the contrapositive. If n = lm for some integers l and m both strictly greater than 1,
then 2l − 1 > 1 and (1 + 2l + 22l + . . . + 2l(m−1) ) > 1

2lm − 1 = (2l − 1)(1 + 2l + 22l + . . . + 2l(m−1) )

So 2lm − 1 has proper divisors, so it cannot be prime.