Lots of remainder 1s
has a remainder of 1 for 5 of the 13 integers from 1 to 13.
What is the smallest integer such that has remainder 1 for exactly 6 of the integers from 1 to
The answer is 65.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
13/n having remainder 1 is equivalent to 13 = 1 mod n.
As we see in the gif,
We may notice that for each n in our range, 13 = 1 mod n implies 12 = 0 mod n.
More generally, for each n and a, a = 1 mod n implies (a-1) = 0 mod n.
Each of the instances of remainder 1s correspond to a divisor of 12, and we further cover all divisors of 12, except for "1".
For example, 13/6 has remainder 1 if and only if 12/6 has remainder 0, but while 12/1 has remainder 0, 13/1 does not have remainder 1 due to the special nature of dividing by 1.
#(Remainder 1s of a) = #(divisors of (a-1)) - 1
The number of instances of remainder 1 of a is equal to the number of divisors of (a-1) minus 1, since the divisor of 1 itself does not count.
Thus, as we are looking for a number with six instances of "remainder 1" we can equivalently look for the smallest number with seven divisors. This unfortunately is not easy, however we may shorten our search by noting a special case: The number of divisors is odd if and only if the number is square. Since if a = b*c then both b and c are divisors, adding 2 to the count. however if b = c, only one gets added to the count.
We use brute force to test square numbers until we hit 7 divisors.
Thus 65 /n will have six instances of remainder 1.
(note, we also found 17 and 37 as the lowest numbers having 4 remainder 1s and 8 remainder 1s, respectively)