Hello!
I thought that I understood most parts of basic modular calculations but then I stumbled on to this
1001a Ξ 1 mod 4920
How do I solve for a? It is supposed to be done without a calculator...
Thank you
Hello!
I thought that I understood most parts of basic modular calculations but then I stumbled on to this
1001a Ξ 1 mod 4920
How do I solve for a? It is supposed to be done without a calculator...
Thank you
You can use the Chinese Remainder Theorem.
$4920 = 2^3\cdot 3 \cdot 5\cdot 41$
So, compute $a \pmod{2^3}$, $a \pmod{3}$, $a \pmod{5}$, and $a \pmod{41}$.
You have
$1001a \equiv a \pmod{8} \Longrightarrow a \equiv 1 \pmod{8} \Longrightarrow a = 8n_1+1$ for some integer $n_1$.
$1001a \equiv 2a \pmod{3} \Longrightarrow a \equiv 2 \pmod{3} \Longrightarrow a = 3n_2+2$ for some integer $n_2$.
$1001a \equiv a \pmod{5} \Longrightarrow a \equiv 1 \pmod{5} \Longrightarrow a = 5n_3+1$ for some integer $n_3$.
$1001a \equiv 17a \pmod{41}$. This one will require the Euclidean Algorithm.
Alternately, you can just solve the whole thing by the Euclidean Algorithm.
Using just the Euclidean Algorithm:
$4920 = 4\cdot 1001 + 916$
$1001 = 1\cdot 916 + 85$
$916 = 10\cdot 85 + 66$
$85 = 1\cdot 66 + 19$
$66 = 3\cdot 19 + 9$
$19 = 2\cdot 9 + 1$
Now, we work backwards:
$\begin{align*}1 & = 19 - 2\cdot 9 \\ & = 19 - 2(66-3\cdot 19) = 7\cdot 19 - 2\cdot 66 \\ & = 7(85-1\cdot 66) - 2\cdot 66 = 7\cdot 85 - 9\cdot 66 \\ & = 7\cdot 85 - 9(916-10\cdot 85) = 97\cdot 85 - 9\cdot 916 \\ & = 97(1001-1\cdot 916) - 9\cdot 916 = 97\cdot 1001 - 106 \cdot 916 \\ & = 97\cdot 1001 - 106(4920 - 4\cdot 1001) = 521\cdot 1001 - 106\cdot 4920\end{align*}$
So, we have $1 + 106\cdot 4920 = 521\cdot 1001$, so $521 \equiv a \pmod{4920}$