# Divisibility Problem

• June 10th 2012, 08:18 AM
mjoshua
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?
• June 10th 2012, 08:27 AM
Plato
Re: Divisibility Problem
Quote:

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: $1,~2,\cdots,~13,~14.$ What do you see?

Now look at this list $13,~14,\cdots,~25,~26.$ What do you see?
• June 10th 2012, 08:33 AM
mjoshua
Re: Divisibility Problem
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?
• June 10th 2012, 09:01 AM
Plato
Re: Divisibility Problem
Quote:

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?
• June 10th 2012, 09:13 AM
mjoshua
Re: Divisibility Problem
Oh right, I mean that makes sense, but what does the proof look like for it?
• June 10th 2012, 09:53 AM
Goku
Re: Divisibility Problem
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 $\frac{n+13}{13}=\frac{n}{13} + 1$ 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... (Thinking)
• June 12th 2012, 10:28 PM
richard1234
Re: Divisibility Problem
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