Kvant Math Problem 2883

The previous solution attempted to prove nonexistence by separating cases according to the prime factorization of $n$.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 24m39s
Source on kvant.digital

Problem

Is there a natural number $n$ such that for some three of its divisors $a$, $b$, $c$, all greater than 1, the product $(a-1)(b-1)(c-1)$ is divisible by $n^2$?

R. Ishkuvatov

All-Russian Mathematics Olympiad (LII, regional stage)

Exploration

The previous solution attempted to prove nonexistence by separating cases according to the prime factorization of $n$. The reviewer correctly pointed out that the main estimates were invalid. A different approach is needed.

The decisive observation is that for a divisor $d$ of $n$, every common divisor of $d-1$ and $n$ must come entirely from the complementary factor $n/d$. This creates a strong restriction on how much of $n$ can divide the product $(a-1)(b-1)(c-1)$.

Problem Understanding

We must determine whether there exists a natural number $n$ and divisors $a,b,c>1$ of $n$ such that

$(a-1)(b-1)(c-1)$

is divisible by $n^2$.

The task is a pure existence question. Either an example must be produced, or all possibilities must be excluded.

Proof Architecture

For each divisor $d$ of $n$, define

$g(d)=\gcd(d-1,n).$

The key facts are:

$g(d)\mid \frac nd,$

and all prime factors of $n$ appearing in $d-1$ already appear in $g(d)$.

Applying this to $a,b,c$ will show that if $n^2$ divides $(a-1)(b-1)(c-1)$, then

$n^2\mid g(a)g(b)g(c).$

Since each $g(d)$ divides $n/d$, it follows that

$n^2\le \frac{n^3}{abc},$

hence

$abc\le n.$

But then

$(a-1)(b-1)(c-1)<abc\le n<n^2,$

which is incompatible with divisibility by $n^2$.

Solution

Assume that there exist a natural number $n$ and divisors $a,b,c>1$ of $n$ such that

$n^2\mid (a-1)(b-1)(c-1).$

For a divisor $d$ of $n$, put

$g(d)=\gcd(d-1,n).$

First, prove that

$g(d)\mid \frac nd.$

Fix a prime $p$, and write

$p^\alpha\parallel n,\qquad p^\beta\parallel d.$

Since $g(d)\mid n$, one has

$v_p(g(d))\le \alpha.$

If $\beta>0$, then $p\mid d$. Because consecutive integers are coprime,

$\gcd(d,d-1)=1,$

so $p\nmid(d-1)$. Hence $p\nmid g(d)$ and

$v_p(g(d))=0.$

Since $\beta\le\alpha$,

$v_p!\left(\frac nd\right)=\alpha-\beta\ge0,$

and therefore

$v_p(g(d))=0\le v_p!\left(\frac nd\right).$

If $\beta=0$, then $p\nmid d$, so

$v_p!\left(\frac nd\right)=\alpha.$

Together with $v_p(g(d))\le\alpha$, this gives

$v_p(g(d))\le v_p!\left(\frac nd\right).$

Thus for every prime $p$,

$v_p(g(d))\le v_p!\left(\frac nd\right).$

Therefore

$g(d)\mid \frac nd.$

Now write

$a-1=g(a)u,\qquad b-1=g(b)v,\qquad c-1=g(c)w.$

Since $g(a)=\gcd(a-1,n)$, dividing $a-1$ by its full gcd with $n$ yields

$\gcd(u,n)=1.$

The same argument gives

$\gcd(v,n)=\gcd(w,n)=1.$

Therefore every prime factor of $n$ occurring in

$(a-1)(b-1)(c-1)$

comes entirely from

$G:=g(a)g(b)g(c).$

Because

$n^2\mid (a-1)(b-1)(c-1)=Guvw,$

and $u,v,w$ are each coprime to $n$, every prime power dividing $n^2$ must already divide $G$. More explicitly, if

$p^\alpha\parallel n,$

then $v_p(u)=v_p(v)=v_p(w)=0$, while

$2\alpha\le v_p\bigl((a-1)(b-1)(c-1)\bigr)=v_p(G).$

Hence $p^{2\alpha}\mid G$. This holds for every prime divisor $p$ of $n$, so

$n^2\mid G.$

Using $g(d)\mid n/d$, we obtain

$$G=g(a)g(b)g(c) \le \frac na\cdot\frac nb\cdot\frac nc = \frac{n^3}{abc}.$$

Since $n^2\mid G$, one has $G\ge n^2$. Consequently,

$$n^2\le G\le \frac{n^3}{abc},$$

which implies

$abc\le n.$

On the other hand,

$(a-1)(b-1)(c-1)<abc,$

because $a,b,c>1$. Combining this with $abc\le n$ gives

$(a-1)(b-1)(c-1)<n.$

Since $a,b,c>1$ are divisors of $n$, necessarily $n>1$. Therefore

$n<n^2,$

and hence

$(a-1)(b-1)(c-1)<n^2.$

A positive integer smaller than $n^2$ cannot be divisible by $n^2$. This contradicts

$n^2\mid (a-1)(b-1)(c-1).$

The contradiction shows that no such natural number $n$ exists. Thus the answer is negative:

$\boxed{\text{There is no natural number }n\text{ with the stated property.}}$

Verification of Key Steps

For every divisor $d$ of $n$, the relation

$\gcd(d-1,n)\mid \frac nd$

is established by comparing $p$-adic valuations. If $p\mid d$, then $p\nmid(d-1)$ and the $p$-valuation of $\gcd(d-1,n)$ is $0$. If $p\nmid d$, then the $p$-valuation of $\gcd(d-1,n)$ is at most the full $p$-valuation of $n$, which equals the $p$-valuation of $n/d$. Hence

$v_p(\gcd(d-1,n))\le v_p(n/d)$

for every prime $p$, proving the divisibility.

The factors

$u=\frac{a-1}{g(a)},\qquad v=\frac{b-1}{g(b)},\qquad w=\frac{c-1}{g(c)}$

are all coprime to $n$. Hence the entire contribution of the primes dividing $n$ is contained in $g(a)g(b)g(c)$. This justifies the deduction

$n^2\mid g(a)g(b)g(c).$

The chain

$$n^2 \le g(a)g(b)g(c) \le \frac{n^3}{abc}$$

is therefore valid, yielding $abc\le n$ and the final contradiction.

Alternative Approaches

The same idea can be expressed prime by prime. For each prime power dividing $n$, the exponent with which it can occur in $d-1$ is bounded by the exponent with which it occurs in the complementary divisor $n/d$. Summing these bounds for the three chosen divisors gives

$n^2\le \frac{n^3}{abc},$

hence $abc\le n$. The inequality

$(a-1)(b-1)(c-1)<abc$

then yields the contradiction exactly as above. The argument presented packages all prime powers simultaneously through the gcds $g(d)$.