Determine all natural numbers$ n> 1$ with the property: For each divisor $d> 1$ of number $n$, then $d - 1$ is a divisor of $n - 1$.
Problem
Source: Czech-Polish-Slovak Junior Match 2015, Individual p5 CPSJ
Tags: divisor, number theory
15.03.2020 14:12
Clearly all primes satisfies the given implication $(1) \;\; d \mid n \;\; \wedge \;\; d>1 \;\;\; \Longrightarrow \;\;\; d-1 \mid n-1$. Assume $1 < d < n$ is a divisor of the composite integer $n$ which satisfies implication (1). Consequently $\frac{n - 1}{d - 1} - \frac{n}{d} = \frac{n - d}{d(d - 1)} \in \mathbb{N}$, yielding ${\textstyle \frac{n - d}{d(d - 1)} \geq 1}$, which implies $d \leq \sqrt{n}$. Moreover, if $p$ is the least prime divisor of $n$, then $p \leq \sqrt{n}$ (with equality iff $n=p^2$), i.e. ${\textstyle \frac{n}{p} \geq \sqrt{n}}$, implying (since ${\textstyle \frac{n}{p}}$ is a divisor of $n$) $n=p^2$. If $n=p^2$, then $d=p$, which means $d - 1 \mid n - 1$ (i.e. $p - 1 \mid p^2 - 1$). Summa summarum, $n$ satisfies implication (1) iff $n$ is a prime or a square of a prime.
02.07.2024 12:30
Much simpler version of EGMO 2024/3. Let $d>1$ divide $n$. Then $\frac{n}{d} = k$ also divides $n$ and hence $\frac{n}{d} - 1 = k-1$ divides $n-1 = dk-1$. So $k-1$ divides $dk-1 = d(k-1) + d-1$ and thus $k \leq d$, i.e. $d\geq \sqrt{n}$. In particular, every prime dividing $n$ is at least $\sqrt{n}$ in size. Now if we assume that $n$ has at least three (not necessarily distinct) prime factors, then their product would be at least $n\sqrt{n} > n$, contradiction. Similarly, if $n$ is a product of two distinct primes, then both are at least $\sqrt{n}$, but one of them is strictly greater, so the product overall exceeds $n$, contradiction. Hence either $n$ is prime (which works, as $d=n$ is the only possibility) or $n$ is a square of a prime (which works, as $d-1 \mid d^2-1$ whenever $n=d^2$).