# SOLUTIONS FOR HOMEWORK 6: NUMBER THEORY

6. (a) Show that if n > 1 is composite, then there exists
d in the range such

that d|n. (Hint: you might want to use proof by contradiction).

Proof by contradiction. Suppose for all d in the range
does not divide

n. In other words, all divisors of n greater than 1 are in fact greater than.
Since n is

composite, there exists an integer e in the range 1 < e < n such that e|n. Then
ef = n for

some integer f. Since f is also a positive divisor of n, it follows from our
assumption that

and .
(Note that we cannot have f = 1 because e < n and we cannot have

f = n because e > 1). But then is a
contradiction. Thus, if n > 1 is

composite, it must admit a divisor in the range
.

(b) Use (a) to show that if n > 1 is not divisible by any integers in the range
, then

n is prime.

Suppose n > 1 is not divisible by any integers in the range
. If n were composite,

then by (a), it would have a divisor in this range, so n must be prime.

(c) Use (b) to show that if n is not divisible by any primes in the range,
then n

is prime.

Proof by contradiction. Suppose n > 1 is not divisible by any primes in the
range.

and that n is composite. By (a), n is divisible by some integer
. Since every

integer > 1 is divisible by at least one prime , there exists a prime p|d, so of
course p|n

since d|n. Since and 2 ≤ p ≤d, we have
is prime and divides n, a

contradiction. This completes the proof.

(d) Use the procedure in (c) to verify that 229 is prime.

We check that 229/p for p = 2, 3, 5, 7, 11, 13 gives non- zero remainder . Since
,

we are done by (c).

(e) Suppose you write down all the primes from 2 to n. We know that 2 is a prime
so we

circle it and cross out all other multiples of 2. The next uncrossed number is 3
and we claim

that 3 therefore must be prime. Explain why. Now cross out all the multiples of
3. The next

uncrossed number is 5 so we claim it must be a prime. We continue in this
fashion until we

get to . Explain why
all the remaining numbers are prime. Carry out this procedure for

n = 100 to find all the primes less than 100. This is called the Eratosthenes
sieve. (You may

want to write them in 10 rows of 10 numbers each).

Once we cross out multiples of 2, 3, . . . , ,
any number that remains does not have a

divisor less than or equal to
so must be prime by
(c).

7. (a) Prove that if n ∈ N, then gcd(n, n + 1) = 1.

Suppose d|n and d|(n + 1). Then d|(n + 1 − n) by Problem 1, i.e. d|1 so d = ±1.
Thus,

gcd(n, n + 1) = 1.

(b) Is it possible to choose 51 integers in the interval [1, 100] such that no
two chosen

numbers are relatively prime? [i.e. is there a subset
with

|S| = 51 such that m, n ∈ S ) => gcd(m, n) > 1?] Prove that your answer is
correct. (Hint:

If you get stuck, recall that an often useful problem- solving strategy is to
attempt a simpler

problem first, so think about 6 integers in [1, 10] for example).

Suppose and |S| = 51. I claim there exists 1
≤n ≤99 such that

n∈ S and n + 1 ∈ S. We can prove this claim by contradiction. Suppose not. Then
if we

list the elements of S in increasing order as
, we have for

1 ≤ k ≤50. Thus, . Since
, it follows that
a contradiction.

Thus, there exists 1 ≤n ≤99 such that n, n + 1 ∈ S. Then gcd(n, n + 1) = 1 by a
previous

problem. So we cannot have a subset of size 51 in {1, 2, 3, . . . , 100} no two
of whose elements

are relatively prime.

8. Show that for n ≥1, in any set of
integers, there is a subset of exactly of

them whose sum is divisible by . (Hint: use
ordinary induction on n).

To ease the notation, let us make a definition. If S is a finite subset of Z,
let us define

to be the sum of its elements. We want to
prove, for n ≥1,

P(n) : If has size
, then there exists
of size
such that
.

Induction on n. Base case n = 1. Given
integers, say a, b, c, at least 2 of

them must have the same parity, by the pigeonhole principle (there are only two
possible

“parity pigeonholes” namely even and odd, so the three “pigeons” (a, b, c)
cannot get three

distinct pigeonholes). So, we take two that have the same parity: their sum is
even, i.e. is

divisible by . This takes care of the base
case.

Induction step. Suppose k ≥1 is some integer such that the proposition is true
for all

subsets of Z of size . Suppose
and
. We are looking for a subset

of size
such that
is divisible by
.

**Step 1. Chop Shop.** If we set aside a random element, say x ∈ S, we
can chop up the

rest of S into two subsets of equal size,
i.e.
is a partition where

. There are many choices for
, x of course, we just

choose any one we like .

**Step 2. A tale of two pigeons.** By the induction hypothesis, there exist
and

of size
such that
and are
divisible by
. It is tempting to

take , but then we will have only that
divides T . Namely we have

and so .
So what is the problem? The problem is that

divides
if and only if 2|(a+b), i.e. if and only if a, b have the same parity. Now,
since

we have only two numbers, a, b, we can’t guarantee they have the same parity!
(conclusion:

not enough pigeons!) Got to get me some more pigeons by golly.

**
Step 3. The magical third pigeon.** The critical step in this problem is to
realize that

if we could find another “pigeon” i.e. another subset of S of size , then inside it we

can find elements that add up to something of the form with c ∈ Z, then among a, b, c

we’ll be able to find two of the same parity. BUT, we have already used up the elements of

and and do not want to disturb them, so we have to make sure that is disjoint from

and (i.e. we don’t have any “interference” when we add up the sums). If you think

about this, then you eventually have the brilliant idea that maybe we should count up how

many elements are left outside to see if we have enough elements left. Well,

That last “!” is a “surprise” not a “ factorial ,” by the
way. In other words, if we gather

together all the elements we have not yet used up, they form a subset

of size , so we can apply the induction step
once again to find a subset
of

size such that
. Now, by construction,
are pairwise disjoint. Now,

among the three numbers , for i = 1, 2, 3, by
the base case, we are guaranteed

two of them add up to an even number, say is
even. Then taking , we

have and
.

9. Suppose x is a real number such that x+1/x is an integer. Show that
is also

an integer for all n ≥1. (Hint: Use complete induction on n).

To ease the notation, let us put α = (x + 1/x) ∈ Z and, for
n ≥1,
. The

proposition is clearly true for n = 1 since .
Let us do n = 2 to see what is involved.

We have , so
. Thus, if ∈ Z, then

since .
So there should be some nice relationship between
and

. Rather, there is a neater relationship
between
and .

Well, let us go to the induction step. We assume, for some integer k ≥1, that
for

1 ≤ j ≤ k. We compute

In other words,

By the (complete) induction step, we know that
, and certainly
so

By the principle of complete mathematical induction , we are done.

10. Here is a “proof” by complete induction that all Fibonacci numbers are even!
Your

job is to explain the error in the argument.

For n ≥ 0, let P(n) be the statement that
is even. We will prove P(n) by complete

induction on n. We check the base case,
is even. Now we move to the induction

step: We must show that if P(j) holds for 0 ≤ j ≤ n, then P(n) holds. Well, if
P(j) holds

for 0 ≤ j ≤ n, then is even because
and
are even by P(n − 1)

and P(n), respectively. By Complete Induction, therefore,
is even for all n ≥ 0.

The error is in the step where P(n − 1) and P(n) are both used. For n = 1, this
requires

both P(0) and P(1) to be true. So, when one wants to do the base case, one needs
to check

both P(0) and P(1). It is not enough to check P(0). Indeed, when one tries to
check P(1),

it turns out to be false, for is odd.

Prev | Next |