Problem A. 843. (January 2023)

A. 843. Let \(\displaystyle N\) be the set of those positive integers \(\displaystyle n\) for which \(\displaystyle n\mid k^k-1\) implies \(\displaystyle n\mid k-1\) for every positive integer \(\displaystyle k\). Prove that if \(\displaystyle n_1,n_2\in N\), then their greatest common divisor is also in \(\displaystyle N\).

(7 pont)

Deadline expired on February 10, 2023.

If \(\displaystyle n\notin N\), then there is a number \(\displaystyle k\) such that \(\displaystyle k^k \equiv 1 \pmod{n}\) but \(\displaystyle k \not \equiv 1 \pmod{n}.\) Hence \(\displaystyle 1 \neq o_{n} (k) \mid k, \varphi(n)\) so \(\displaystyle \varphi(n)\) has a common prime divisor with \(\displaystyle k.\) Meanwhile, \(\displaystyle k\) is relatively prime to \(\displaystyle n.\) It follows that \(\displaystyle \varphi(n)\) has a prime divisor not dividing \(\displaystyle n.\)

The prime divisors of \(\displaystyle \varphi(n)\) are either prime divisors of \(\displaystyle n\), or prime divisors of \(\displaystyle q-1\) where \(\displaystyle q\) is a prime divisor of \(\displaystyle n\). Therefore, if \(\displaystyle n\notin N\), then there exist primes \(\displaystyle q|n\) and \(\displaystyle p|q-1\) such that \(\displaystyle p\nmid n\).

Conversely, suppose there exist primes \(\displaystyle q|n\) and \(\displaystyle p|q-1\) but \(\displaystyle p\nmid n\). Then we will construct a \(\displaystyle k\) such that \(\displaystyle n|k^k-1\) but \(\displaystyle n\nmid k-1\), thus proving that \(\displaystyle n\notin N\).

Let \(\displaystyle e\) be the exponent of \(\displaystyle q\) in the prime factorization of \(\displaystyle n.\) If \(\displaystyle k\) is congruent to \(\displaystyle 1\) modulo all prime powers dividing \(\displaystyle n\) besides \(\displaystyle q^e,\) then by the Chinese Remainder Theorem, it suffices that \(\displaystyle k \not \equiv 1 \pmod{q^e}\) and \(\displaystyle k^k \equiv 1 \pmod{q^e}.\)

There exists a primitive root \(\displaystyle g\) modulo the prime power \(\displaystyle q^e\). Let

\(\displaystyle k \equiv g^{\frac{q^{e-1}(q-1)}{p}} \pmod{q^e},\)

and let \(\displaystyle p|k\). This is possible by the Chinese Remainder Theorem, as we assumed that \(\displaystyle p\) is not among the prime divisors of \(\displaystyle n\). And now \(\displaystyle k \not \equiv 1 \pmod{q^e}\) and \(\displaystyle k^k \equiv 1 \pmod{q^e}\) are satisfied.

Thus, we can conclude that \(\displaystyle N\) is the set of numbers \(\displaystyle n\) for which for all primes \(\displaystyle q|n\) and \(\displaystyle p|q-1\), it follows that \(\displaystyle p|n\) too. Then, the statement of the problem easily follows: if \(\displaystyle n_1, n_2\in N\), and \(\displaystyle n=\gcd(n_1, n_2)\), then for all primes \(\displaystyle q|n\) and \(\displaystyle p|q-1\), \(\displaystyle q\) divides both \(\displaystyle n_1\) and \(\displaystyle n_2\), so because \(\displaystyle n_1, n_2\in N\), it follows that \(\displaystyle p|n_1\) and \(\displaystyle p|n_2\), so \(\displaystyle p|n\). This means that \(\displaystyle n\in N\) too.

—

This problem is a slightly changed version of a problem, created by Evan Chen, from the Online Math Open.

Statistics:

11 students sent a solution.
7 points:	Bodor Mátyás, Diaconescu Tashi, Móricz Benjámin, Németh Márton, Szakács Ábel, Varga Boldizsár, Wiener Anna.
6 points:	Sida Li.
1 point:	1 student.
0 point:	2 students.

Problems in Mathematics of KöMaL, January 2023