A teacher wrote a large number on the board and asked the students to tell about the divisors of the number one by one.
The 1st student said, "The number is divisible by 2." The 2nd student said, "The number is divisible by 3." The 3rd student said, "The number is divisible by 4." . . . (and so on) The 30th student said, "The number is divisible by 31.
The teacher then commented that exactly two students, who spoke consecutively, spoke wrongly.
Which two students spoke wrongly?
Taken from here
Okay so the first step is to realize that:
The secret numbers are consecutive so one is even and one is odd.
Also,
It can't be any two consecutive numbers if it is not divisible by 2 and 3. For example, it also wouldn't be divisible by 6 or 8 or 9, etc, which would violate the condition.
Hence,
These two numbers cannot have multiples that are less than 31. Eliminating 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, and 15.
Also, we see that
It can't be like the number 21 because if it's divisible by 3 and 7, it will be divisible by 21.
Eliminating all of those, we get that the answer is
Students number 16 & 17.
Since the actual question is: Can you find the two numbers? Which two students spoke wrongly?, technically no one has answered it! The right answer is:
Yes, the 15th and 16th students.
Solution:
Since no other student was wrong, the first inference is that these two consecutive divisors cannot have any multiples <=30.
2 being the smallest possible multiplier, that means both must be greater than 15. Clearly any two consecutive numbers have to be an even-odd pair. If that odd number had any (odd) factors, the large number would need to be indivisible by at least one of those factors. But that would have caused an earlier student to have been called wrong. So this must be a prime number. Similarly, the even number in the pair cannot have any odd factors either, so it can only be a power of 2.
The only available primes in the range are 17, 19, 23 and 29. Of the numbers adjacent to these primes only 16 is a power of 2. All the remaining numbers 18,20,22,24,28,30 have at least one odd factor.
So the consecutive numbers can only be (16,17) which were called out by the 15th and 16th students.
The numbers that don't divide the one on the board can't be less than 16, otherwise also their multiples won't divide it. Similarly, neither can be a non-prime with multiple distinct prime factors, as that would mean there's a smaller divisor not dividing the number on the board. Since one of the numbers must be even, it's a power of 2.
- If $2^k-1=p^r (k>3)$:
$2^k=p^r+1$ (the right hand side must be divisible by 4 - only possible if $r$ is odd)
$2^k=(p+1)(p^{r-1}-p^{r-2}+...-...-p+1)$ (the second factor is odd, so $p+1=2^k, r=1$)
However, there's no solution (Mersenne prime less than a valid power of 2) from 16 to 31.
- If $2^k+1=p^r (k>3)$:
$2^k=p^r-1$
$2^k=(p-1)(p^{r-1}+p^{r-2}+...+p+1)$ (either $r=1$ or $r$ is even)
If $r$ is even, both $p^{r/2}-1$ and $p^{r/2}+1$ are powers of 2.
However, there's no solution from 16 to 31 in this case.
In short, one must be a power of 2 and the other a prime. 16 and 17 are the only duo satisfying the conditions, which corresponds to Student 15 and 16.
