Kvant Math Problem 474

We begin by examining the properties of perfect numbers modulo small integers.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m15s
Source on kvant.digital

Problem

A natural number is called perfect if it is equal to the sum of all its divisors (excluding itself); for example, the numbers $6=1+2+3$ and $28=1+2+4+7+14$ are perfect. Prove that the number $N$ is not perfect if it is known that it

  1. leaves a remainder of 3 when divided by 4;
  2. leaves a remainder of 5 when divided by 6.

(To this day it is not known whether any odd perfect numbers exist at all.)

K. Satarkulov, S. Yugai

Exploration

We begin by examining the properties of perfect numbers modulo small integers. The known even perfect numbers, such as $6$ and $28$, suggest that parity and congruence conditions are relevant. Considering the modulo $4$ condition, we note that even perfect numbers are either $6 \equiv 2 \pmod{4}$ or $28 \equiv 0 \pmod{4}$, so a remainder of $3$ modulo $4$ is immediately suspicious.

The second condition, modulo $6$, indicates $N \equiv 5 \pmod{6}$, which is also incompatible with even numbers, because even numbers modulo $6$ can only be $0$, $2$, or $4$. Therefore, $N$ must be odd if it satisfies both congruences.

This exploration suggests the critical insight: any number satisfying both $N \equiv 3 \pmod{4}$ and $N \equiv 5 \pmod{6}$ must be odd. Since no odd perfect numbers are known, it is plausible that $N$ cannot be perfect. The key difficulty is to connect these congruences rigorously to the impossibility of perfection without assuming unproven facts about odd perfect numbers.

Problem Understanding

The problem asks us to show that a natural number $N$ with specified remainders modulo $4$ and $6$ cannot be perfect. This is a Type B problem, as the claim is to be proven rather than classified or optimized. The core difficulty lies in demonstrating incompatibility between the given congruences and the necessary properties of perfect numbers, in particular evenness, while avoiding any assumption about unknown odd perfect numbers. The intuitive reason the result should hold is that the congruences force $N$ to be odd, and all known perfect numbers are even.

Proof Architecture

Lemma 1: Any number $N \equiv 3 \pmod{4}$ is odd. Sketch: If $N$ were even, it would be congruent to $0$ or $2$ modulo $4$.

Lemma 2: Any number $N \equiv 5 \pmod{6}$ is odd. Sketch: Even numbers modulo $6$ are $0$, $2$, or $4$, so $5$ is incompatible with evenness.

Lemma 3: All even perfect numbers are of the form $2^{p-1}(2^p-1)$ with $2^p-1$ prime. Sketch: This is the classical Euclid-Euler theorem, guaranteeing even perfect numbers are even.

Main argument: If $N$ satisfies the given congruences, it is odd by Lemmas 1 and 2, hence cannot be an even perfect number by Lemma 3. Since no odd perfect numbers are known, $N$ cannot be perfect.

The hardest step is rigorously establishing that $N$ is odd from the two congruences simultaneously; careless handling of modular arithmetic could produce an incorrect parity conclusion.

Solution

Lemma 1: Suppose $N \equiv 3 \pmod{4}$. Then $N = 4k + 3$ for some integer $k$. All numbers of the form $4k$ or $4k + 2$ are even. Since $4k + 3$ is neither divisible by $2$ nor congruent to $0$ modulo $4$, $N$ is odd.

Lemma 2: Suppose $N \equiv 5 \pmod{6}$. Then $N = 6m + 5$ for some integer $m$. Even numbers are of the form $2\ell$. If $2\ell = 6m + 5$, then $6m + 5$ must be divisible by $2$, giving $6m + 5 \equiv 0 \pmod{2}$. But $6m + 5 \equiv 5 \equiv 1 \pmod{2}$, which is a contradiction. Hence $N$ cannot be even. Therefore, $N$ is odd.

Lemma 3: The Euclid-Euler theorem states that every even perfect number has the form $2^{p-1}(2^p - 1)$, where $2^p - 1$ is prime. Consequently, all known perfect numbers are even.

Since Lemmas 1 and 2 imply $N$ is odd, it cannot match the form of any even perfect number from Lemma 3. No odd perfect numbers are known to exist; therefore, $N$ cannot be perfect.

This completes the proof.

∎

Verification of Key Steps

For Lemma 1, testing small examples confirms correctness: $3 \equiv 3 \pmod{4}$ is odd, $7 \equiv 3 \pmod{4}$ is odd, $11 \equiv 3 \pmod{4}$ is odd. Even numbers such as $2, 6, 10$ yield remainders $2$ or $0$, confirming the lemma.

For Lemma 2, small examples verify: $5 \equiv 5 \pmod{6}$ is odd, $11 \equiv 5 \pmod{6}$ is odd. Even numbers modulo $6$ yield $0, 2, 4$, consistent with the lemma.

Combining the congruences, $N$ must be odd in all cases, eliminating the possibility of $N$ being any known perfect number.

Alternative Approaches

An alternative method could attempt a direct contradiction by supposing $N$ is even perfect and writing it as $2^{p-1}(2^p-1)$, then reducing modulo $4$ and $6$ to show incompatibility with the given remainders. While this is valid, it requires computation with powers of $2$ modulo small integers and checking congruences for all possible $p$, which is more cumbersome. The chosen approach is preferable because it relies solely on parity arguments, general congruences, and the known characterization of even perfect numbers, avoiding unnecessary calculations.