An integer n≥2 is called resistant, if it is coprime to the sum of all its divisors (including 1 and n). Determine the maximum number of consecutive resistant numbers. For instance: * n=5 has sum of divisors S=6 and hence is resistant. * n=6 has sum of divisors S=12 and hence is not resistant. * n=8 has sum of divisors S=15 and hence is resistant. * n=18 has sum of divisors S=39 and hence is not resistant.
Problem
Source: Switzerland 2019, final round, problem 8
Tags: number theory, Divisibility, sum of divisors
Darghy
04.03.2019 21:21
The answer is 5, achieved for example with the integers 575 to 579.
Let d(n) denote the sum of the divisors of n.
I claim that if n is even, then n can only be resistant if it is either a square or twice a square. This holds since if we have a prime p>2 such that vp(n)=k where k is odd, then the sum of divisors of pk is d(pk)=pk+pk−1+⋯+1, an even integer. Since d(n) is multiplicative, d(n)=d(pk)⋅d(npk), thus d(n) is divisible by 2, but so is n, so gcd(n,d(n))≥2 and thus n is not resistant.
Now note that if we have 6 consecutive resistant integers, then 3 of them are even and must be of the form x2 or 2y2. It is also clear that the difference between any two consecutive even square numbers is at least 12, and the difference between any 2 numbers of the form 2y2 is at least 6. Thus if the 3 resistant even integers are 2k, 2k+2 and 2k+4, then either 2k=x2, 2k+2=2y2 and 2k+4=z2 for some x,y,z, or 2k=2x2, 2k+2=y2, 2k+4=2z2 for some x,y,z. In both cases 2k and 2k+4 are both of the same form (either x2 or 2y2), but differ by less than 6, contradiction. This proves that the answer is ≤5.