Browse · MathNet
PrintVMO
Vietnam algebra
Problem
An integer sequence is defined as follows: and
a. Prove that if then for each positive integer , the sum of divisors of the following number is divisible by 24
b. Find all pairs such that are perfect squares for infinitely many numbers .
a. Prove that if then for each positive integer , the sum of divisors of the following number is divisible by 24
b. Find all pairs such that are perfect squares for infinitely many numbers .
Solution
Lemma 1. If a positive integer satisfies then the sum of its positive divisors is divisible by 24.
Proof. Indeed, if is a divisor of then is also a divisor of . Because so it cannot be a perfect square, which means the sum of its divisors can be divided into pairs of the form Note that and so the sum above is divisible by 3. On the other hand, and , which implies so the above sum is also divisible by 8. Since then the above sum is divisible by 24 and the lemma is proved.
a. Back to our problem, denote , we need to prove that is divisible by 24. We also have so according to the lemma, we need to show .
Consider the period of the remainder when being divided by 3 of the sequence , note that we have 2, 0, 2, 0, 2, 0, ... this sequence is periodic with period 2 and
Similarly, consider the remainder of when being divided by 8, note that we have which means this sequence is periodic with period 3 and It follows that is both divisible by 3, and 8, so and a) is proved.
b. Now, we prove the following lemma.
Lemma 2. Consider the integer sequence satisfying then the following quantity is constant Proof. Indeed, we have the following transformation The above equality holds for all so where is a constant.
Thus, there exists such that . We have where , for all .
Since is an increasing integer sequence so it is unbounded, thus is increasing and unbounded. It is also clear that if is a perfect square then .
Hence, for infinite values of . Clearly, this case only happens when so We have so , but then , i.e. . We also have Notice that so , which implies . By direct checking, the case and has no solution. So , which implies so it's easy to see that .
Therefore, is the only satisfying pair.
Proof. Indeed, if is a divisor of then is also a divisor of . Because so it cannot be a perfect square, which means the sum of its divisors can be divided into pairs of the form Note that and so the sum above is divisible by 3. On the other hand, and , which implies so the above sum is also divisible by 8. Since then the above sum is divisible by 24 and the lemma is proved.
a. Back to our problem, denote , we need to prove that is divisible by 24. We also have so according to the lemma, we need to show .
Consider the period of the remainder when being divided by 3 of the sequence , note that we have 2, 0, 2, 0, 2, 0, ... this sequence is periodic with period 2 and
Similarly, consider the remainder of when being divided by 8, note that we have which means this sequence is periodic with period 3 and It follows that is both divisible by 3, and 8, so and a) is proved.
b. Now, we prove the following lemma.
Lemma 2. Consider the integer sequence satisfying then the following quantity is constant Proof. Indeed, we have the following transformation The above equality holds for all so where is a constant.
Thus, there exists such that . We have where , for all .
Since is an increasing integer sequence so it is unbounded, thus is increasing and unbounded. It is also clear that if is a perfect square then .
Hence, for infinite values of . Clearly, this case only happens when so We have so , but then , i.e. . We also have Notice that so , which implies . By direct checking, the case and has no solution. So , which implies so it's easy to see that .
Therefore, is the only satisfying pair.
Final answer
(2, 3)
Techniques
Recurrence relationsσ (sum of divisors)Divisibility / FactorizationModular Arithmetic