Results 1 to 3 of 3
Like Tree6Thanks
  • 3 Post By SlipEternal
  • 3 Post By SlipEternal

Thread: Modular calculations by hand with large numbers

  1. #1
    Newbie
    Joined
    Aug 2017
    From
    Linkooping
    Posts
    5

    Modular calculations by hand with large numbers

    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


    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    Re: Modular calculations by hand with large numbers

    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.
    Last edited by SlipEternal; Oct 25th 2017 at 06:20 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    Re: Modular calculations by hand with large numbers

    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}$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Feb 3rd 2016, 08:22 PM
  2. Replies: 6
    Last Post: Feb 19th 2015, 10:14 PM
  3. Replies: 5
    Last Post: Aug 24th 2011, 04:09 PM
  4. Help with multiplying large numbers by hand
    Posted in the Algebra Forum
    Replies: 6
    Last Post: Feb 16th 2009, 03:31 PM
  5. Large Calculations to Hours, Minutes, Seconds
    Posted in the Math Topics Forum
    Replies: 6
    Last Post: Nov 4th 2008, 07:38 AM

/mathhelpforum @mathhelpforum