Difference between revisions of "2022 SSMO Speed Round Problems/Problem 6"

@@ Line 1: / Line 1: @@
-==Problem==
-Find the smallest odd prime that does not divide <math>2^{75!} - 1</math>.
-==Solution==
-Let this odd prime be <math>p</math>.
-Note that <math>2^{75!} - 1</math> is divisible by <math>p</math> if
-<cmath>
-^{75!} \equiv 1 \pmod{p}
-</cmath>
-or <math>p - 1 \mid 75!</math>.
-As such, <math>p</math> is the smallest prime of the form <math>2q + 1</math> where
-<math>q > 75</math> is also prime.
-This is called a \textit{safe} prime in literature and checking
-that <math>\boxed{167}</math> is the first such <math>p</math>.

Page