Problem 3. We call a positive integer n peculiar if, for any positive divisor d of n , the integer d ( d + 1) divides n ( n + 1). Prove that for any four different peculiar positive integers A , B , C and D , the following holds:
gcd( A, B, C, D ) = 1 .
Here gcd( A, B, C, D ) is the largest positive integer that divides all of A, B, C and D .
Solution 1
Let be an arbitrary peculiar number and let where be its prime factorization. Then, we have which implies . Since , this actually implies that and hence . Therefore, by the minimality of . Hence, is either a prime or of the form where and are primes.
Let be a peculiar number. Note that being a peculiar number implies and . Since we obviously can't have , we may assume that . If we have , we get which contradicts . Hence, .
Let . We must have because . Additionally, since , we must have which implies that .
Let . It is evident that . On the other hand, we have . Combining these results together, we may conclude that . Therefore, .
Hence, for all primes , there are at most distinct primes such that is peculiar. In particular, one such that and one such that . This implies the result.
Solution 2
What a joke! Let be peculiar and let be its smallest prime divisor. Then, letting it follows that divides Evidently, divides hence divides It follows that so One may also trivially see that by choosing
So, any peculiar number is either prime, or of the form for some prime numbers which satisfy and Therefore, it suffices to show that for a fixed prime there exist at most two primes with the previous properties. Assume, for the sake of contradiction, that at least three such primes exist. Evidently,
By the pigeonhole principle, two of them are both greater or both smaller than First, assume that Fix arbitrarily. Since then so because we must have Also, so from we have Thus, the primes satisfy the system of congruences Therefore, at least one of the primes is greater than which is absurd, because for each
Now, assume that Fix Evidently, so which gives us Also, because then so from we get So, satisfies the congruences so However, so this would imply for both which is absurd.
Solution 3
The point is to characterize all peculiar . I claim that either with prime, or where and are both prime. Oh and also , which I forgot. (-1 maybe)
If
is prime or
, we are done.
Otherwise suppose
is not prime and let
be the smallest prime factor. Note
. Then
In particular let
. Notice
hence
.
Since
and
is prime, it follows that
.
Note that
and so the prime factorization of
contains only primes at least
. Hence if the value is composite, it must be at least
. Thus:
which is a contradiction. Hence
is a prime, with
being of the form
.
We'll replace variables now: let
and let
.
Clearly
; otherwise
and since
we fail.
Now notice
Thus
Looking back, we find
where
and
are both prime.
Now suppose there is a prime
which divides four different peculiar positive integers.
- The only prime which could be a multiple of is itself.
- The only numbers of the form with and prime that are multiples of must have or , yielding two other numbers.
Thus obtaining four different numbers is impossible (the above counts three). We are done
Solution 4
Let , where , taking gives:
This means , obviously impossible unless where is another prime such that . If , we have:
which is impossible.
If is of the form , we have . If , then as , which means , , however isn't a peculiar number. Therefore,
So let . Now, we also have:
If , we have , impossible as it's greater, which means . Due to size reasons, we have .
Now, we can have at most three peculiar numbers divisible by . The only possible prime is , and the other two peculiar numbers can be , where .