Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 SSMO Team Round Problems/Problem 12"

(Created page with "==Problem== What is the smallest positive integer <math>n</math> with 3 positive prime factors such that for all integers <math>k</math>, <math>k^n \equiv k \pmod n</math>?...")
 
 
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
 +
Let the prime factors of <math>n</math> be <math>p</math>, <math>q</math>, and <math>r</math>. For this to be true, note that <math>p - 1 | n - 1</math> and similarly with <math>q</math> and <math>r</math>. Obviously <math>n</math> has to be squarefree, so <math>n = pqr</math>. WLOG let <math>p < q < r</math>. It is easy to see that if <math>p = 2</math> is one of the factors we have a contradiction. We can arrive at similar contradictions with pairs of factors such as <math>(3, 7),(3,13), (3,19)</math> and <math>(5,11)</math>. This eliminates most possibilities, so we can manually check triples now. <math>(3, 5, 17)</math> does not work, and neither does <math>(5, 7, 13)</math>. Finally, we note that <math>(3, 11, 17)</math> does indeed work, and our answer is <math>n = 3 \cdot 11 \cdot 17 = \boxed{561}</math>.
 +
 +
~SMO_Team

Latest revision as of 14:41, 10 September 2025

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_SSMO_Team_Round_Problems/Problem_12&oldid=260275"