Difference between revisions of "2024 SSMO Team Round Problems/Problem 8"
(Created page with "==Problem== Three integers <math>0\le a\le b\le c< 229</math> satisfy the congruence <math>n^3 \equiv 1 \pmod{229}.</math> Given that <math>71^2 - 3</math> and <math>107^2 +...") |
|||
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
| + | Note that <math>n^3\equiv1\pmod{229}\implies (n^3-1)\equiv0\pmod{229}.</math> Consider the complex third roots of unity <math>1</math> and <math>\frac{-1\pm i\sqrt{3}}{2}.</math> They can be defined based on <math>\frac12,\sqrt{-1},</math> and <math>\sqrt3.</math> From the given multiples of <math>229,</math> we can <math>\sqrt{3}\equiv71\pmod{229}</math> and <math>i\equiv107\pmod{229}</math> since they function like square roots. In addition, <math>229</math> is odd so <math>2^{-1}</math> exists. We have <math>i\sqrt{3}\equiv107\cdot71\equiv269\pmod{229}.</math> Thus, <math>\frac{-1+i\sqrt{3}}{2} \equiv 134\pmod{229}</math> and <math>\frac{-1-i\sqrt{3}}{2}\equiv94\pmod{229}.</math> So, <math>a = 1,b = \boxed{94},</math> and <math>c = 134.</math> | ||
| + | |||
| + | ~SMO_Team | ||
Latest revision as of 14:38, 10 September 2025
Problem
Three integers 
satisfy the congruence 
Given that 
and 
are both multiples of 
find the value of 
Solution
Note that 
Consider the complex third roots of unity 
and 
They can be defined based on 
and 
From the given multiples of we can 
and 
since they function like square roots. In addition, 
is odd so 
exists. We have 
Thus, 
and 
So, 
and 
~SMO_Team
