Forum — Daily Challenge
    • Categories
    • Recent
    • Tags
    • Popular
    • Users
    • Groups
    • Login

    Better way to solve systems of linear congruences in general

    Module 5 Day 10 Challenge Part 7
    2
    4
    16
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • P
      professionalbronco M0★ M1★ M2★ M3 M5★
      last edited by

      Note: this requires knowledge about modular inverses.
      Suppose you have the system

      $$x\equiv 3\pmod{4} $$ $$x\equiv 2\pmod{11} $$

      which was used in the mini-question.
      By CRT (Chinese Remainder Theorem), we know that there is a unique solution modulo \(44\) that satisfies the system. From the first congruence, we see that \(x\) can be expressed as \(4a+3\) where \(a\) is a positive integer.
      Substituting this into the second congruence, we get

      $$4a+3\equiv 2\pmod{11}\implies 4a\equiv -1\pmod{11}\implies 4^{-1}\cdot 4a\equiv -1\cdot 4^{-1}\pmod{11}\implies a\equiv 8\pmod{11}. $$

      This means that \(a=11b+8\), where \(b\) is another positive integer. Substituting this into \(x=4a+3\), we get \(x=4(11b+8)+3=44b+35\). Therefore, \(x\equiv 35\pmod{44}\). From this, you would get the answer of \(0\) for the mini-question.

      Anyways, I made this post to emphasize a different way to solve systems of linear congruences, which I found from AoPS.
      (I usually use this method to solve modular congruences, but if numbers are small enough, I usually end up using guess and check. Also, mods, can you check this?)

      The Daily Challenge with Po-Shen Loh is the best!
      aops user = captainnobody

      1 Reply Last reply Reply Quote 0
      • 西瓜西
        西瓜 M0★ M1★ M2★ M3★ M4★ M5★
        last edited by

        This is a very nice and interesting way to solve modular congruences!

        What is this method called?

        Hello, this is 西瓜.

        P 1 Reply Last reply Reply Quote 0
        • P
          professionalbronco M0★ M1★ M2★ M3 M5★ @西瓜
          last edited by

          @西瓜 There isn't a name. This method can be used to solve systems of modular congruences in general: bigger numbers, etc.

          The Daily Challenge with Po-Shen Loh is the best!
          aops user = captainnobody

          1 Reply Last reply Reply Quote 0
          • 西瓜西
            西瓜 M0★ M1★ M2★ M3★ M4★ M5★
            last edited by

            Okay, thanks! 🙂 @professionalbronco

            Hello, this is 西瓜.

            1 Reply Last reply Reply Quote 0

            • 1 / 1
            • First post
              Last post
            Daily Challenge | Terms | COPPA