# Teacher, teacher on the wall, Who's the dumbest of them all?

A maths teacher writes a very large number on the blackboard and asks her pupils (of whom there are $n$ in the room) about its factors.

The first pupil says, "The number is divisible by 2."
The second says, "The number is divisible by 3."
The third says, "The number is divisible by 4."
The fourth pupil says, "The number is divisible by 5."
$...$
The $n$th pupil says, "The number is divisible by ($n+1$)."
The teacher says, "You were all right except for two of you, who spoke consecutively."

Given this information, what can you say about:

• the value of $n$
• which two pupils were wrong?

If you want to list all possibilities, then we can limit $n$ to be less than $100$ to make the problem finite. However, there is a general answer for which values are possible, which works for arbitrarily large $n$.

Don't worry about what the number on the blackboard is! You could find its smallest possible value in each case using the Chinese Remainder Theorem, but that would be boring and tedious.

I'll upvote any answer which is correct and relies only on pencil, paper, and logic without resorting to computer power. The green tick will go to whichever answer gives the correct solution in the most simple and elegant way.

NB: this is a maths puzzle and not a maths problem. There's a nice 'aha!' which narrows down the possibilities considerably, and the nature of the final solution is quite surprising.

• For the general case, are we assuming at least 5 students? – StephenTG Aug 10 '15 at 13:08
• There is no unique answer to 'Which two pupils were wrong?' Are you expecting one? Reasoning: Let b be the number on the board, let n= 4. Suppose b = 6, then pupils 3 and 4 were wrong. Suppose b = 10, then pupils 2 and 3 are wrong. – chasly from UK Aug 10 '15 at 14:24
• @chaslyfromUK Consider a function f(n) that for every number n gives you which pupils are wrong. Does such a function exist, if no, why not, if yes, (how) can you compute it? – Alexander Aug 10 '15 at 14:27
• @Alexander - Here's a definition of function. "A technical definition of a function is: a relation from a set of inputs to a set of possible outputs where each input is related to exactly one output." goo.gl/A8cEd4 --- There is no such function in this case. I have just disproved its existence by providing a counterexample. – chasly from UK Aug 10 '15 at 14:57
• @chaslyfromUK The question says "what can you say about which two pupils were wrong?" You can say something about a number (e.g. provide a small set it must belong to) without being able to determine it uniquely. – Rand al'Thor Aug 10 '15 at 15:29

If $x$ has at least two distinct prime factors, that is $x = p^n * q^m * r$, with $p, q$ primes, $n, m \ge 1$, and $r$ not divisible by $p$ or $q$, then $(p^n * r) | z$ and $(q^m * r)|z$ implies $(p^n * q^m * r = x)|z$.

Therefore, if $x$ is a wrong answer, and all answers $< x-1$ were correct answers, $x$ cannot have two distinct prime factors; $x$ must be either a prime number or a power of a prime number. Further, if $x$ is a wrong answer, then $2x$ is also a wrong answer.

Since exactly two answers $\le n+1$ were incorrect, and the two incorrect answers were consecutive, the two incorrect numbers are $x$ and $x+1$ with $x \ge 2$, and $n \le 2x-2$, and both $x$ and $x+1$ are either primes or powers of primes.

The only two consecutive primes are $2$ and $3$; other than this at least one of $x$ and $x+1$ is a non-trivial power of a prime. So we have one number $p^k$, where $p$ is a prime and $k \ge 2$, and $p^k \pm 1$ which is a prime or a power of a prime.

Assume $p \ge 3$, which implies $p$ is odd: $p^k \pm 1$ is even, therefore it is not a prime but must be power of $2$. Therefore, one of the incorrect numbers must be a power of two: The incorrect answers are $2^k$ and $2^k \pm 1$. If $2^k \pm 1$ is a prime, then it is either a Mersenne prime or a Fermat prime; the only known Fermat primes are $3, 5, 17, 257, 65537 = 2^1 + 1, 2^2 + 1, 2^4 + 1$ and $2^{16} + 1$; the smallest known Mersenne primes are $2^k - 1$ for $k = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657$.

If we assume that the number of students is less than the world population, the possibilities are $(4,5)$, $(16,17)$, $(256,257)$, $(65536,65537)$, $(3,4)$, $(7,8)$, $(31,32)$, $(127,128)$, $(8191,8192)$, $(131071,131072)$, $(524287, 524288)$, $(2147483647,2147483648)$, where the other number is a prime.

If the other number is a prime power, then the only pair is $(8,9)$ (Mihăilescu's theorem, better known as Catalan's conjecture but proven in 2002).

Since $3$ is also a Fermat prime, in total the possibilities are $(8,9)$, all numbers $(2^k, 2^k + 1)$ where $2^k + 1$ is a Fermat prime, and $(2^k, 2^k - 1)$ where $2^k - 1$ is a Mersenne prime.

So the first possible pairs of wrong answers and the only that are possible on earth with actual humans are $(2,3)$, $(3,4)$, $(4,5)$, $(7,8)$, $(8,9)$, $(16,17)$, $(31,32)$, $(127,128)$, $(256,257)$, $(8191,8192)$, $(65536,65537)$, $(131071,131072)$, $(524287,524288)$, $(2147483647,2147483648)$.

The possible values for $n+1$ are $[3 \ldots 15], [17 \ldots 61], [128 \ldots 253], [257 \ldots 511]$ etc. and the possible values for $n$ are $[2 \ldots 14], [16 \ldots 60], [127 \ldots 252], [256 \ldots 510]$. So we don't have a class of $15$ students, or $61$ to $126$ students, or $253$ to $255$ students, or $511$ to $8190$ students.

We could probably use the fact that the number actually fit on the board to exclude some large numbers.

• +1; this is a very complete answer! It'd look nicer if you added some LaTeX maths formatting though :-) – Rand al'Thor Aug 10 '15 at 21:09
• Didn't know you could do this on this site... – gnasher729 Aug 10 '15 at 21:15
• For large values of 1, you could have just two students, as neither 2, nor 3 would divide into 1. Zero being the counterpoint small value ... – Philip Oakley Aug 11 '15 at 14:32
• +1 Great answer! Good observation on Mihăilescu's theorem. – Marconius Aug 12 '15 at 16:59

The consecutive numbers need both be powers of primes.

Why? First consider this:

If ($a\mid x$) and ($b\mid x$) and ($a$ and $b$ are coprime) then ($ab\mid x$)

I'm not sure if this a well known Lemma but I think it is so I don't need to prove it.

Now assume one of the consecutive numbers (call it $x$) is not a power of a prime. you can then always write $x=pq$ where $p$ and $q$ are coprime meaning that according to my Lemma that $x$ also divides the number, CONTRADICTION.

Knowing that one of the numbers is divisible by 2 we now know that that number is actually always of the form $2^x$.

And because of Catalan's conjecture we know that the other number is $3^2$ or a prime number.

This answers which two pupils were wrong. What's left to determine is what this means for $n$. Unfortunately I don't know this (yet)

Also nice to know that if these consecutive numbers are $x$ and $x+1$ then the number on the board is divisible by $LCM(1,2,...,x-2,x-1)$

• +1; this answer is correct on which two pupils were wrong. As for the possibilities for $n$, there are a lot of them! – Rand al'Thor Aug 10 '15 at 15:34
• A prime of the form (2^n)-1 is a mersenne prime. In which case we know that n is prime. If (2^n)+1 is prime we have a fermat prima and know that n=2^k for some k. – Taemyr Aug 11 '15 at 9:19
• LCM(1,2,...,x−2,x−1) can be replaced by LCM(1,2,...,n)/2x, if x is prime or LCM(1,2,...,n)/(2x+2) if x+1 is prime. – Taemyr Aug 11 '15 at 9:23

One of the two pupils that are wrong could be a prime. The other one cannot be prime unless $n<3$, it has to be an even number. So it has to have more occurrences of at least one prime factor than every number smaller than it. This requires it to be the highest number of the form $2^x$ that you have in the sequence.

As an example, consider the students saying: 2, 3, 4, 5, 6, 7. In this case, it has to be 4,5 that are wrong, every other combo makes other students wrong as well.

This also means there are $n$s that are impossible - like 15 students (15,16 -> 15 is not prime). 16 students works again, 17 being prime. Likewise, between 63 and 127 there's a huge gap, because 64 has no adjacent prime.

On the other hand, some instances of $n$ have two possibilities.

2,3,4,5,6,7,8,9


Here it could be 7,8 that are wrong, or 8,9. Why 8,9, there's no prime in it? Because it has two numbers with more occurrences at least one prime factor than every number smaller than it. ($3\times 3$ and $2\times 2\times 2$). Such edge cases should be really few.

EDIT: To generalize, you need any two adjacent numbers that only have exactly one prime factor, and have more occurrences of it than any other number in the list. This means that you can limit your search to the upper half of the list, but including the middle element, if available.

• hmm I did not think of any adjacent pure powers of numbers case... I wonder if there are any ridiculous adjacent pairs x^n = y^m +1... that would be cool... (where x and y are prime) – Going hamateur Aug 10 '15 at 14:57
• +1; this is correct, but not as neatly expressed (IMO) as some of the other answers. – Rand al'Thor Aug 10 '15 at 15:46

First, for each incorrect pupil, the number he said is a power of a prime. Otherwise its factors were already mentioned and were correct.

One of those two said an even number, so one of the incorrect numbers is a power of 2. It is also the largest power of 2 smaller than n, otherwise next power of 2 would be incorrect as well. So the incorrect number $2^t$ is greater than $\frac n 2$.

The other pupil named a number of either $2^t + 1$ or $2^t - 1$ and that number has to be a power of a prime. Probably any power. For example a group of 14 pupils where pupils 7 and 8 are wrong (number is not divisible by 8 and 9).

• +1; this is correct, but you can say a little more. "Probably any power" isn't right; in fact that number has to be prime unless it's 9. – Rand al'Thor Aug 10 '15 at 15:39
• If at least one of them is a prime, then that prime can't be found among the others' divisors as a factor more than once.

• If at least one is a compound (which is true), that compound's divisors can be found separately, but not at once. For that, this number must be a power of a prime.

The compound prime power is a power of 2, and the other is an odd prime (or they're 8 and 9). Both can't be non-trivial prime powers unless they're 8 and 9, because:

• If $n, m > 1, p > 2$ and $p^n-1 = 2^m$, $n$ is either odd and so is $(p^n-1)/(p-1)$, making $n=1$ (contradiction), or $n$ is even and both $p$^$(n/2)$-1 and $p$^$(n/2)$+1 are powers of 2, making them 2 and 4 respectively.

• If $n, m > 1, p > 2$ and $p^n+1 = 2^m$, then $p^n = 2^m-1$, so $m$ is odd (contradiction otherwise), and $p^n - 1 = 2^m-2 = 2* [2$^$(m-1)] = 2* [2$^$((m-1)/2) + 1] * [2$^$((m-1)/2)-1]$. Since $p^n - 1$ shouldn't be divisible by 4, $n$ is also odd. $p+1$ is a power of 2. $p^n+1$/($p+1$) is odd, so it must be 1, which is a contradiction.

In short, the wrong number duo can be 4-5, 7-8, 8-9, 16-17 or 31-32 if there're fewer students than 100 and more than 3 (3 < $n$ < 100), but both have to be greater than $n/2$ no matter what $n$ is.

In addition, if the prime is the smaller out of the two, the other's power value must be a prime, and if it's bigger, the power must be a power of 2 (respectively Mersenne and Fermat primes), both of which can be proven when the relevant expression is expanded. So the greatest such possible duo can be the wrong divisors, because other candidates would be too small.

The most obvious answers would be 2-3 (for 2 students), 3-4 (3 to 4 students) and 4-5 (4 to 6 students). In addition, 8-9 would be feasible for 8 to 14 students. The generalized rule above applies to all the other solutions.

• +1; this is correct except for a few small/trivial cases you've missed (like 2 and 3 with n=2). – Rand al'Thor Aug 10 '15 at 15:37
• Edited to cover the trivial cases. – Nautilus Aug 11 '15 at 8:14

I am not quite sure if I am correct, but lets see.

My guess is: It has sth. to do with the primes.

I started with the number x, lets say x = 5 (it doesn't really matter, if its small enough). Then I iterate through the pupils and check if x can be divided by the number said. If not I mutliply it with the number.

#1 pupil has number = 2
can't be divided so x = 10  (x*2)
#2 pupil has number = 3
can't be divided so x = 30
#3 pupil has number = 4
can't be divided so x = 120
#4 pupil has number = 5
can be divided, so x stays at 120
.
.
.


With this scheme every prime would not be a divisor of x. So my idea was to find a pupil number which is not a prime an still no divisor AND is directly before a prime.

The number 16 is one of them, followed by the prime number 17. With this method x =1081080 until pupil #15 and this value for x can't be divided by 16 or 17.

So the last two pupils are wrong, and the very last said number must be a prime.

Edit:

And I have found a sequence: This happens every $y = 2^z$ for z = the previous y

z=2;   y=4
z=4;   y=16
z=16;  y=256
z=256; y=65536
.
.


All these y values are followed by a prime!

• The thing is, with a sufficiently large number, y - 2 will be a factor of x. Hmm. – jimsug Aug 10 '15 at 14:02
• It can also be preceeded by a prime: 3,4 7,8 31,32 etc. I endorse an answer involving powers of 2's adjacent to primes with the Going Hamateur seal of approval § – Going hamateur Aug 10 '15 at 14:07
• @Goinghamateur You are totally right, I just forget about the predecessor – Wa Kai Aug 10 '15 at 14:23
• Some of this is right, but it's not complete. Remember you don't have to worry about the number x! And "the very last said number must be a prime" (i.e. n+1 is prime?) is wrong. – Rand al'Thor Aug 10 '15 at 15:41

Because the two pupils are consecutive one of those is divisible by 2. Let's call that pupil $x$. This means that $x/2$ also can't be a divisor because if $x/2$ is a divisor and $2$ is a divisor then $x$ is also a divisor, contradiction. This either means that the consecutive number are $x$ and $x/2$ or that the number is not divisible by $2$. Since the next number can never be double the previous number it must automatically mean that the number is not divisible by $2$ and, because it needs to be consecutive with another, also not divisible by $3$. This also means that the only valid $n$ is when $n=2$ because a number not divisible by $2$ can't be divisible by $4$ also giving more incorrect statements

• 12 is not divisible by 8 but it is divisible by 4, so your first argument isn't necessarily true – StephenTG Aug 10 '15 at 12:28
• I don't understand what you're saying. All i say is that if $a$ and $b$ are divisors of a number then $a \cdot b$ is also a divisor of that number – Ivo Beckers Aug 10 '15 at 12:30
• If we use 12 as that number (just as an example), and have a = 2, b = 4, then a and b are divisors of 12, but a*b is not – StephenTG Aug 10 '15 at 12:32
• But a*b does not equal 12. In my example I say the following. Let's say that x=12. This means that the number is not divisable by 12. This means that number also not divisable by 6. 6 and 12 are not consecutive so this can't be the case. – Ivo Beckers Aug 10 '15 at 12:35
• Aah. now I understand. You're right. thanks for making me see that. I guess my answer is incorrect. I'l just leave it here for others who might make the same mistake – Ivo Beckers Aug 10 '15 at 12:39

The incorrect students are any two students adjacent to each other who each hold a number which is the highest power of a prime of all students.

Of course, it is trivial that one of those students must hold a power of two. Two odd numbers can't be adjacent to eachother.

After that, it is clear that any number adjacent to the highest power of two held which is a power of a prime must be the highest power of that prime. We would hit a higher power of two before we would hit a higher power of any other prime.

Knowing this, n can be arbitrarily high. Sure there are ranges n can't be, such as from 65 to 127 or so ( I haven't done the exact math here but anywhere where the highest power of 2 is not next to an included power of a prime) but we will always eventually find a power of a prime next to a power of 2.

• +1; this is correct but not complete since there are some restrictions on n. Welcome to Puzzling.SE btw :-) – Rand al'Thor Aug 10 '15 at 21:06
• Ivo Beckers answer identifies Catalans conjecture as relevant. In particular it tells us what "the highest power of that prime" is. – Taemyr Aug 11 '15 at 9:29

I'm kind of late (almost 3 years late!), but I solved this without looking at others' answers. I found two abstract conditions necessary to qualify a candidate n value, and two specific conditions sufficient to disqualify one.

Two integers in a row will always contain one odd and one even - that is, a number that has 2 as a factor. In order for both to not be factors of the number written on the board, and all the rest to be factors, both must be powers of prime numbers. Because one is divisible by 2, it must be a power of 2; otherwise, there will be a higher power of 2 in the range of interest. Likewise, the odd number must be a power of another prime, so that there are no equal or higher powers of its factors in the range 2 to n+1.

Therefore, if n is legitimate for this scenario to play out, then

1. one of the "dumb students" will be the student who named the highest power of 2
2. the other "dumb student" will be one who named a power of an odd prime, either 1 less or 1 greater than the greatest power of 2
3. both of these numbers will be greater than n/2
4. if n+1 is a power of 2, then n must be a power of an odd prime, and
5. if n/2+1 is a power of 2, then n/2+2 must be a power of an odd prime

• Impressive slavish adherence to "pencil, paper, and logic" notwithstanding, it really would be helpful if you transcribed your solution as text. :) – Rubio Mar 31 '18 at 15:25

Nice puzzle.

The maximum number of pupils in the class is

14

We can argue that certain pupils must be correct. The argument goes this way: Say 2,3,6 are called. If 6 was wrong, 2 or 3 must also be wrong. But that's impossible since the two wrongs must be consecutive. Hence, 6 must be correct, and also 2 and 3.

A variation of this argument applies to square numbers: If 2 and 4 are called, we know that 2 must be correct. (but not necessarily 4).

Another observation is that once a divisor is proven correct via the argument above, it can never be false again, regardless how many pupils call something later.

Now we can play a reverse Sieve of Eratosthenes until no two consecutive wrongs are possible:

• n=2: Both wrong :-)

• n=3: 2 must be correct

• n=4: nothing new. Two solutions exist.

• n=5: 2,3 must be correct, hence 6 also.

...

• n=7: 8 is called, so 4 must be correct. 5 also because both neighbors are already correct.

• n=8: Two solutions exist, either (7,8 wrong) (8,9 wrong)

...

• n=13: 14 is called, which makes 7 correct. 14 is also correct since 2 and 7 are already correct. Only the (8,9 wrong) solution exists.

• n=15: 16 is called, which makes 8 correct. Now we have a contradiction. Let's write the number and highlight those already proven correct: 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

From now on, whenever an even number n is added, is must be correct since n/2 is already marked as correct.

(maybe this could have been formulated a bit shorter, but still, the arguments work)

• Think of 16 pupils, with the number not being divisible by 16 and 17. – Alexander Aug 10 '15 at 14:23
• Eww. You're right. I mistakenly marked 16 as correct. This would happen for any 2^n where one of its neighbors is prime. Hm, this makes it more complicated. Good catch. – Gully Aug 10 '15 at 15:00
• Some of your argument is good, but the final answer is incorrect :-( – Rand al'Thor Aug 10 '15 at 15:33

(answers are highlighted with bold. (corresponds to encircling on paper). "/∶" means "not divisible by" (didn't find the proper symbol).)

In mathematical terms, the puzzle looks like this:

The number on the blackboard is divisible by everything in the list 2,3,4...n+1 except 2 consecutive numbers (let's call them m,m+1).

What can we say about them?

1. The number is divisible by 2 but not divisible by m
=> m*2 isn't present in the list1
2. The number is divisible by anything less than m,m+1 but not divisible by them
=> m,m+1 can't be factored by the (different) numbers in the list2
____specifically: one of the m,m+1 is even
____=> m/2|(m+1)/2 isn't present in the list - unless the other multiplier is 2 as well

=> There are only a few possibilities for m,m+1:

• 2,3 => n+1<4 (2 students, both wrong. ha-ha) N=1 ROFLMAO
_____________________________________all possibilities though are: N∈N, N/∶2,3
• 3,4 => n+1<6 (n<5) | => n=3 N=2 big number indeed
_____________________________________all possibilities: N=2k,k/∶2,3
________________| => n=4 (2,3,4,5) => N=10
_____________________________________all possibilities: N=10k,k/∶2,3
• 4,5 => n+1<8 => n can be at most 6 (list entry n+1 =7)

The last case requires study in more detail:

Possible values for n:
- 4 at least <= to include "4,5"
=> n=4 (2,3,4,5) => N=6k,k/∶2,5
=> n=5 (2,3,4,5,6) => same as above
=> n=6 (2,3,4,5,6,7) => multiplier=LCM(2,3,6,7)=42 =>
_________________=> N=42k,k/∶2,5

My, my. Big numbers these days...

1(If the number isn't divisible by 2 (m=2), this stands, too: 4 cannot be present)
2(without loss of generality, by two different numbers in the list: if e.g. (m+1)=k*k*l, k*l is also present in the list and is not m)

• Now, let me double-check this... – user15507 Aug 10 '15 at 17:06
• Fixed the last case analysis, added a few notes on special cases. Looks good. – user15507 Aug 10 '15 at 18:33

Edited to resolve a prior issue with an incorrect solution:

So, basically, for incorrect students p and p+1, 1 <= p < n, n may lie within the range p+1 < n+1 < (p+1)*2.
Both p+1 and p+2 are either prime or have a single prime factor.
This would mean that the pair p, p+1, for n up to 100, is as follows (p,p+1)
1,2 [divisors 2,3; n=2]
2,3 [divisors 3,4; n=3 or 4]
3,4 [divisors 4,5; 3 < n < 7]
6,7 [divisors 7,8; 6 < n < 13]
7,8 [divisors 8,9; 7 < n < 27]
15,16 [divisors 16,17; 15 < n < 31]
30,31 [divisors 31,32; 30 < n <61]

• Sorry, this is wrong. Try e.g. n=32 with the incorrect students being 16 and 17. There's no upper bound on n. – Rand al'Thor Aug 10 '15 at 20:37
• If student 17 is incorrect, then the number is not divisible by 18, yet it is divisible by both 2 and 9 (students 1 and 8 are correct). How is that possible? – Wolf Larson Aug 10 '15 at 20:49
• I meant the students who talk about divisibility by 16 and 17 (so students 15 and 16, if you like). – Rand al'Thor Aug 10 '15 at 21:07
• I still find that confusing. The number is divisible by 32 (n=32 would mean it is divisible by 2..33, except for 16 and 17), but not by 16. Do you mean n=30? – Wolf Larson Aug 10 '15 at 21:15
• Yes, n=30 (or anything down to 16); sorry. – Rand al'Thor Aug 10 '15 at 21:20

I'm Back on a computer!

So we know the two students who claimed wrong claimed wrong consecutively. We can say that these two students claimed that the numbers $a$ and $b$ were factors of the number written on the board by the teacher, which in reality it wasn't. The first thing to note is that one of these numbers, either $a$ or $b$ must be even, and one of these numbers must be odd. The second thing to note is that both $a$ and $b$ must be factored into only one type of prime, eg they must be a prime number raised to some power. To prove this, we can assume the contrary and say that $a$ can be factored to $ppqqq$ where $p$ and $q$ are primes. $pp$ will be smaller than $a$, but we know that all numbers smaller than $a$ were accepted by the teacher as being a factor of the number on the board. Similarly, $qqq$ will be accepted by the teacher as being a factor of the number on the board. If both $pp$ and $qqq$ are accepted as being a factor, then $a$ must also be a factor, breaking our assumption. Therefore both $a$ and $b$ must be some prime raised to a power. Because one of these is even and one of these is odd, the even claim must be a power of $2$, and the odd claim must be a power of an odd prime number.

We know immediately some restrictions upon $n$. Firstly, it must be less than $2a$, and less than $2b$, because we know the number on the board is not divisible by either $a$ or $b$. But I believe this is the only restriction upon $n$.

• I'm not sure what to make of this ... you tell me to ignore most of your post! I'll wait a while in the hope that you'll access SE not on your phone and improve the formatting to make your answer clearer :-) – Rand al'Thor Aug 10 '15 at 15:38