Page 1 of 2 12 LastLast
Results 1 to 15 of 17
Like Tree13Thanks

Math Help - modulo help

  1. #1
    Super Member
    Joined
    Sep 2008
    Posts
    612

    modulo help

    22x = 1(mod27)

    how would i work this out?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: modulo help

    You can find x as follows. Suppose x = \alpha_0 + 3\alpha_1 + 3^2\alpha_2. Then x \equiv \alpha_0 \pmod{3} and x \equiv \alpha_0 + 3\alpha_1 \pmod{9}. So, you can solve the equation in steps. First, let's consider the equation mod 3, then mod 9, then mod 27.

    22x \equiv x \pmod{3}

    22x \equiv 4x \pmod{9}

    So, x \equiv 1 \pmod{3} shows that \alpha_0 = 1. Then 4(1+3\alpha_1) \equiv 1 \pmod{9} shows that 3\alpha_1 \equiv 6 \pmod{9}, so \alpha_1 = 2.

    Then, finally, 22x = 22(1 + 3\cdot 2 + 9\alpha_2) = 22\cdot 7 + 198 \alpha_2 \equiv 19 + 9\alpha_2 \pmod{27}. So, 9\alpha_2 \equiv 9 \pmod{27} shows that \alpha_2 = 1. Then, x = 1 + 3\cdot 2 + 9\cdot 1 = 16.

    Now, you can check your answer: 22\cdot 16 = 352 = 13\cdot 27 + 1.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: modulo help

    Here is an alternate approach: Write 22 in base-3. So, 22 = 211_3 = 1 + 3\cdot 1 + 9\cdot 2 and x = (\alpha_2\alpha_1\alpha_0)_3 = \alpha_0 + 3\alpha_1 + 9\alpha_2.

    Now, multiply the two numbers together:

    \begin{array}{cccccc} & & & 2 & 1 & 1 \\ \times & & & \alpha_2 & \alpha_1 & \alpha_0 \\ \hline & & & 2\alpha_0 & \alpha_0 & \alpha_0 \\ & & 2\alpha_1 & \alpha_1 & \alpha_1 & 0 \\ + & 2\alpha_2 & \alpha_2 & \alpha_2 & 0 & 0 \\ \hline & ? & ? & 0 & 0 & 1\end{array}

    This addition should feel familiar from multiplying two numbers base-10. Only now, for each column, you record the result (mod 3) and carry each multiple of 3. So, the right-most column shows that a_0 = 1. Plugging that in, you have 1+\alpha_1 \equiv 0 \pmod{3}, so \alpha_1 = 2. Now, 1+2 = 3. Divide the result by 3 and that is the amount you are "carrying" to the left. So, you are carrying 1 since you had one 3 from that column. So, the third column is the sum 1 + 2\alpha_0 + \alpha_1 + \alpha_2. You want that sum (mod 3) to be zero. So, 1+2(1) + (2) + \alpha_2 = 5+\alpha_2 \equiv 0 \pmod{3} shows that \alpha_2 = 1. Plugging that in, you have x = 1 + 3\cdot 2 + 9\cdot 1 = 16, which is the same result as the other method.
    Thanks from Tweety and topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2008
    Posts
    612

    Re: modulo help

    why would you choose mod 3 and mod 9 ? where did you get these numbers from ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: modulo help

    It comes from looking at numbers in different bases. 27 = 3^3, so consider numbers in base-3. If the problem had been 11x \equiv 37 \pmod{1000}, I would have suggested looking at the equations mod 10 and mod 100.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,987
    Thanks
    1650

    Re: modulo help

    They are factors of 27: 3(9)= 27.
    Thanks from SlipEternal and topsquark
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: modulo help

    Quote Originally Posted by HallsofIvy View Post
    They are factors of 27: 3(9)= 27.
    If you are learning the Chinese Remainder Theorem, then HallsofIvy brings up a good point, and this is the way you want to think about it.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,068
    Thanks
    372
    Awards
    1

    Re: modulo help

    Quote Originally Posted by SlipEternal View Post
    Here is an alternate approach: Write 22 in base-3. So, 22 = 211_3 = 1 + 3\cdot 1 + 9\cdot 2 and x = (\alpha_2\alpha_1\alpha_0)_3 = \alpha_0 + 3\alpha_1 + 9\alpha_2.

    Now, multiply the two numbers together:

    \begin{array}{cccccc} & & & 2 & 1 & 1 \\ \times & & & \alpha_2 & \alpha_1 & \alpha_0 \\ \hline & & & 2\alpha_0 & \alpha_0 & \alpha_0 \\ & & 2\alpha_1 & \alpha_1 & \alpha_1 & 0 \\ + & 2\alpha_2 & \alpha_2 & \alpha_2 & 0 & 0 \\ \hline & ? & ? & 0 & 0 & 1\end{array}

    This addition should feel familiar from multiplying two numbers base-10. Only now, for each column, you record the result (mod 3) and carry each multiple of 3. So, the right-most column shows that a_0 = 1. Plugging that in, you have 1+\alpha_1 \equiv 0 \pmod{3}, so \alpha_1 = 2. Now, 1+2 = 3. Divide the result by 3 and that is the amount you are "carrying" to the left. So, you are carrying 1 since you had one 3 from that column. So, the third column is the sum 1 + 2\alpha_0 + \alpha_1 + \alpha_2. You want that sum (mod 3) to be zero. So, 1+2(1) + (2) + \alpha_2 = 5+\alpha_2 \equiv 0 \pmod{3} shows that \alpha_2 = 1. Plugging that in, you have x = 1 + 3\cdot 2 + 9\cdot 1 = 16, which is the same result as the other method.
    Does this always work? It doesn't bear any resemblance to the method for the Chinese Remainder theorem that I looked up about a year ago.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: modulo help

    Why factor 27? Why can't Bézout's identity be used?
    Thanks from Tweety
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: modulo help

    Quote Originally Posted by topsquark View Post
    Does this always work? It doesn't bear any resemblance to the method for the Chinese Remainder theorem that I looked up about a year ago.

    -Dan
    Given a modular equation of the form ax \equiv b \pmod{n} where a,b,n are all constants and \gcd(a,n) = \gcd(b,n) = 1, then let n = p_1p_2\cdots p_k be the prime factorization of n. Note that we are choosing an order for the prime factors of n. Then, a,b,x can be expressed by a sum of this form:

    a = \alpha_0 + \alpha_1p_1 + \alpha_2p_1p_2 + \cdots + \alpha_{k-1}\left(\prod_{i = 1}^{k-1}p_i\right) where \alpha_i \in \mathbb{Z}, 0\le \alpha_i < p_{i+1} for all i = 0,1,\ldots, k-1. (And similar sums for for b,x)

    Note: This assumes that 0 \le a<n, 0 \le b<n,\text{ and }0 \le x<n.

    This is similar to writing a number in a different base, only each digit is changing bases. Then you can figure out the multiplication

    Edit: This is currently not correct... I will revisit it later.

    \begin{array}{cccccccc} & & & & \alpha_{k-1} & \cdots & \alpha_1 & \alpha_0 \\ \times & & & & \chi_{k-1} & \cdots & \chi_1 & \chi_0 \\ \hline & & & & \chi_0 \alpha_{k-1} & \cdots & \chi_0 \alpha_1 & \chi_0 \alpha_0 \\ & & & \chi_1 \alpha_{k-1} & \chi_1 \alpha_{k-2} & \cdots & \chi_1 \alpha_0 & 0 \\ & & & \vdots & \cdots & \vdots & \cdots & 0 \\ + & \chi_{k-1}\alpha_{k-1} & \cdots & \chi_{k-1}\alpha_1 & \chi_{k-1}\alpha_0 & 0 & \cdots & 0 \\ \hline & ? & \cdots & ? & \beta_{k-1} & \cdots & \beta_1 & \beta_0\end{array}

    where in the i-th column from the right, you record the sum of the digits \pmod{p_i}, and you "carry" the coefficient of p_i from that sum.

    --I will revisit this later. I am not doing this quite right. There is a way to make this process precise, but I am not there yet. Currently, this process can fail if n is not a power of a single prime.
    Last edited by SlipEternal; November 14th 2013 at 11:36 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: modulo help

    Ok, here is another attempt at it:

    Let n = \prod_{i=1}^m p_i as in the post above (which is an ordering of the prime factors of n).

    Then let a = \sum_{i = 0}^{m-1} \alpha_i \left(\prod_{j = 1}^i p_j \right), \forall 0 \le i < m, 0 \le \alpha_i < p_{i+1}.

    Let x = \sum_{i = 0}^{m-1} \chi_i \left(\prod_{j = 1}^i p_j \right), \forall 0 \le i < m, 0 \le \chi_i < p_{i+1}.

    Let b = \sum_{i = 0}^{m-1} \beta_i \left(\prod_{j = 1}^i p_j \right), \forall 0 \le i < m, 0 \le \beta_i < p_{i+1}.

    Then

    ax = \sum_{i=0}^{m-1} \left[ \left(\sum_{j=0}^{i}\alpha_i\chi_j \left(\prod_{k=1}^j p_k \right) \right) + \left(\sum_{j=0}^{i-1}\alpha_j\chi_i \left(\prod_{k=1}^j p_k\right) \right) \right] \left(\prod_{k=1}^i p_k \right)

    So, the multiplication would need additional rows for the addition. The i-th column from the right (corresponding to the coefficient of p_1\cdots p_{i-1}) would look like this:

    \begin{array}{cc} & c_i \\ & \alpha_{i-1}\chi_0 \\ & \alpha_{i-1}\chi_1p_1 \\ & \alpha_{i-1}\chi_2p_1p_2 \\ & \vdots \\ & \alpha_{i-1}\chi_{i-1}p_1p_2\cdots p_{i-1} \\ & \chi_{i-1}\alpha_0 \\ & \chi_{i-1}\alpha_1p_1 \\ & \vdots \\ + & \chi_{i-1}\alpha_{i-2}p_1\cdots p_{i-2} \\ \hline & \beta_{i-1}\end{array}

    where c_i is the carry from the column to the right. Here, you want that sum to be congruent to \beta_{i-1} \pmod{p_i} and the carry c_{i+1} will be the greatest integer less than or equal to that sum divided by p_i.

    While it may not look like it, this method is actually very similar to the Chinese Remainder Theorem (you can use the theorem to prove this process works).
    Last edited by SlipEternal; November 14th 2013 at 07:14 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: modulo help

    Quote Originally Posted by SlipEternal View Post
    Given a modular equation of the form ax \equiv b \pmod{n} where a,b,n are all constants and \gcd(a,n) = \gcd(b,n) = 1, then let n = p_1p_2\cdots p_k be the prime factorization of n.
    I still claim that when \gcd(a,n) = 1, the simplest way to solve the equation is through Bézout's identity and the extended Euclidean algorithm.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: modulo help

    22x=1(mod27)

    From Euclidean algorithm:
    27=1*22+5
    22=4*5+2
    5= 2*2+1

    Substituting successiveley gives:
    1=9*27-11*22
    1-(-11)22=9*27
    x=-11

    It’s a little short on detail, but it illustrates a standard method.
    Thanks from Tweety, emakarov and topsquark
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    659
    Thanks
    271

    Re: modulo help

    Hi,
    Here's yet another approach:
    Since 22 is prime to 27, 22 has a multiplicative inverse mod 27, say x. With more arithmetic than I like to do you get x = 16. So just multiply both sides of your congruence by 16 and you're done.

    Alternatively, since -5 is the same as 22 mod 27, the original congruence becomes -5x = 1 (mod 27) or 5x = -1 (mod 27). Now I'm willing to do arithmetic to find the inverse of 5 mod 27. Of course, I need check only x's prime to 27. So the relevant multiples of 5 are 5, 10, 20, 25, 35, 40, 50, 55; whoa, stop. 55=5*11 is 1 mod 27. So x = -11 (mod 27) = 16 (mod 27).
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Sep 2008
    Posts
    612

    Re: modulo help

    Quote Originally Posted by Hartlw View Post
    22x=1(mod27)

    From Euclidean algorithm:
    27=1*22+5
    22=4*5+2
    5= 2*2+1

    Substituting successiveley gives:
    1=9*27-11*22
    1-(-11)22=9*27
    x=-11

    It’s a little short on detail, but it illustrates a standard method.

    Hello,

    Thank you, I understand this method, and got up to


    1 = 9*27 -11*22,

    but I do not understand how you know that x = - 11? Can you please explain?


    Thank you.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Modulo
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 7th 2010, 05:14 PM
  2. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  3. Modulo
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: November 25th 2009, 06:35 AM
  4. a modulo m
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 19th 2008, 09:38 PM
  5. CNT - Modulo
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 9th 2007, 11:30 PM

Search Tags


/mathhelpforum @mathhelpforum