2024 SSMO Team Round Problems/Problem 12

Problem

What is the smallest positive integer $n$ with 3 positive prime factors such that for all integers $k$ , $k^n \equiv k \pmod n$ ?

Solution

Let the prime factors of $n$ be $p$ , $q$ , and $r$ . For this to be true, note that $p - 1 | n - 1$ and similarly with $q$ and $r$ . Obviously $n$ has to be squarefree, so $n = pqr$ . WLOG let $p < q < r$ . It is easy to see that if $p = 2$ is one of the factors we have a contradiction. We can arrive at similar contradictions with pairs of factors such as $(3, 7),(3,13), (3,19)$ and $(5,11)$ . This eliminates most possibilities, so we can manually check triples now. $(3, 5, 17)$ does not work, and neither does $(5, 7, 13)$ . Finally, we note that $(3, 11, 17)$ does indeed work, and our answer is $n = 3 \cdot 11 \cdot 17 = \boxed{561}$ .

~SMO_Team

Page

Toolbox

Search

2024 SSMO Team Round Problems/Problem 12

Problem

Solution