Hello. This is Tenmei Watanabe from Dragon Blog. From this time on, I would like to create a dragon game that mixes multiple technical terms.
As a theme, I was planning to create a concept that combines linear congruence, Fermat's little theorem, and Fibonacci sequence, but it was more difficult than I expected, so I decided to start with the first two (linear congruence). I would like to mix up the formula and Fermat's little theorem. First, we will explain the technical terms and play the actual game.
In number theory, we place great importance on the concept of division. In other words, when one number is divided by another number, the remainder is 0. In prime factorization, 91 is divisible by 7 and 13.
It's a bit difficult, but "a is congruent to b modulo m" means a ≡ b (mod m). Here, using a real number example, if a = 92, b = 8, and m = 7, then 92 ≡ 8 (mod 7).
92 – 13 x 7 = 8 – 7 x 1 = 1 mod 7. This means that 92 and 8 each have a remainder of 1 when divided by 7. In other words, 92 and 8 are congruent (same) modulo 7. We use three lines ≡ to represent the sameness. Here, ab is divisible by m. 92-8=84 is 7×12, 92-8=84 is a multiple of 7, and when divided by 7, the remainder is 0.
Now, imagine a clock as a common example. On a 24-hour clock, the hands at 3 o'clock and 15 o'clock will point at different points. That is, 3 and 15. However, if it is a 12-hour clock, I think the hands will point to the same number 3 at 3 o'clock and 3 o'clock. 3:00 and 15:00 are 3:00 a.m. and 3:00 p.m., so if the clock is set every 12 hours, it would point to the same 3:00.
15:00 is one revolution in 12 hours, and 15:00 - 12:00 is 3:00. In the example of a and b from earlier, we can say that 15 o'clock ≡ 3 o'clock (mod 12 o'clock), and 15 o'clock is congruent with 3 o'clock modulo 12 o'clock. 15−3=12×1.
Let me give you another example. Suppose we have the formula 5a + 7b = 17. If you are an intuitive person, you will know that 5 x 2 + 7 x 1 = 17 is one answer.
Here, if we use the mod from earlier, the right side will be 17 mod 7. 17 – 7 x 2 ≡ 3 mod 7, so the remainder when you divide 17 by 7 is 3. Next, we don't know if 5a on the left side is divisible by 7, so let's call it 5a (mod 7). Next, +7b is a multiple of 7 and is an integer, so it is divisible by 7 and has a remainder of 0. So, if we compare the values remaining on both sides, we get 5a (mod7) ≡ 3 (mod7).
Next, find a. It's a little complicated, but let's multiply both sides by 3. 5a x 3 (mod 7) ≡ 3×3 (mod 7). 5a x 3 ≡ 15a ≡ 14a + a ≡ a ≡ 3 x 3 (mod 7) ≡ 9 (mod 7) ≡ 7 + 2 (mod 7) ≡ 2 (mod 7). The reason why we multiplied by 3 is based on Euclid's mutual division method.
7=5×1+2 → Move 5×1 to the left and flip it over → 2=7-5
5=2×2+1 → Move 2×2 to the left and flip it over → 1=5-2×2
1=5-2x(7-5) 2=7-5 substituted into one side of 2×2
=5-2×7+2×5
=3×5-2×7
=1
Here, c=3, d=-2 is the answer to 5c + 7d = 1. 5 x 3 = 1 mod 7, and the right side is 1, so if you multiply both sides by 17 like the original equation 5a + 7b = 17, you get 5 x (3 x 17) + 7 x (-2 x 17) = 1 x 17. 3 x 17 (mod7) ≡ 51 ≡ 7 x 7 + 2 ≡ 2 mod 7.
On the other hand, (-2) x 17 (mod 7) ≡ -34 ≡ -6 +(-7 x 4) ≡ -6(mod7). You can leave it as -6 mod 7 here, but setting it to -6 + 7 ≡ 1 (mod 7) will make it a positive value. Therefore, a = 2 mod 7, b = 1 mod 7.
In other words, by multiplying both sides of 5a + 7b ≡ 17 (mod 7) by 3 (however, do not multiply the mod 7 by 3), 5 x 3a + 7 x 3b ≡ 17 x 3 (mod 7) is calculated as a ≡ 2 mod 7, and by substituting this a into the first 5a of 5a + 7b = 17, we can find b ≡ 1 mod 7. Here, the answer holds either 2 + 7 ≡ 9 mod 7, or 1 – 7 ≡ -6 (mod 7). Do the math yourself on this point! !
Another important point is the idea of the greatest common divisor. The greatest common divisor is 16 and 24, which can be factorized as 16 = 2x2x2x2 and 24 = 2x2x2x3, so 2x2x2 = 8, which is common to both, is the greatest common divisor. In fact, 16÷8=2 has a remainder of 0, 24÷8=3 has a remainder of 0, and 8 evenly divides 16 and 24.
Here, if 5a ≡ (17 mod 7), then if the greatest common divisor of 17 and 7, which is a prime number, is 1, there is only one answer. In other words, a ≡ 2 mod 7. However, if 5a ≡ 16 (mod 24), as we found earlier, the greatest common divisor of 16 and 24 is 8, so we can find 8 answers. Let's check this out for ourselves.
This time it was long, so I only explained the technical terminology (linear congruence). Next time, I would like to investigate Fermat's little theorem and mix "linear congruence" and "Fermat's little theorem." In my opinion, I'm also good at economics, so I think it would be interesting to mix linear congruence with economics terminology.
Additionally, I would like to mix in some humor that will make you laugh while reading this blog. That's all for now. See you next time! ! Mathematics blew away! ! See you soon.
