Thread: Divisibility Problem

A list consists of 14 consecutive positive integers. Which of the following could be the number of integers in the list that are divisible by 13?

Why would the answer be One or Two? How can I show that None is not the answer?

Originally Posted by mjoshua

A list consists of 14 consecutive positive integers. Which of the following could be the number of integers in the list that are divisible by 13? Why would the answer be One or Two? How can I show that None is not answer?

List the first fourteen: What do you see?

Now look at this list What do you see?

The first list has a 13 and the second list has two numbers, 13 and 26, divisible by 13. So that's how we prove 1 or 2 numbers will be divisible by 13??? Also, how can we show that there will always be at least one number that will be?

Originally Posted by mjoshua

The first list has a 13 and the second list has two numbers, 13 and 26, divisible by 13. So that's how we prove 1 or 2 numbers will be divisible by 13??? Also, how can we show that there will always be at least one number that will be?

Well it does not prove it. But help to see how things work.
How 'far apart' are two multiples of thirteen?

Oh right, I mean that makes sense, but what does the proof look like for it?

You could try something like this:

Suppose you have 14 consecutive positive integers i.e. n, n+1, n+2 ....... n+13.

Case 1: n is divisible 13

Then n+13 is divisible by 13 since and we already assumed n is divisible by 13.

So we proved we can have 2 factors, i.e n and n+13

Case 2: n is not divisible 13

Since n is not divisible by 13 we have,

n = 13k + r where 0< r < 13 and k is an Integer
n + r = 13k which implies that n+r is divisible by 13 where 0 < r < 13

So 1 of your numbers from n+1, n+2.... ,n+12 is divisible by 13.

Not sure whether this is good prove or not... but hopes it helps...

You can use a Pigeonhole-type argument to claim that "none" cannot be the answer.

"1 or 2" works. Consider the following sequences of 14 integers:


1,2,...,14
13,14,...,26