Hello. This is Tenmei Watanabe from Dragon Blog. Last time, I explained keywords for dragon games. According to this, he explained the linear congruence formula a ≡ b (mod m), where a and b are congruent by modul m, and a – b = my. In other words, we can say that a and b have the same remainder when divided by m.
https://nabenekocom.blogspot.com/2024/02/i-will-explain-primary-congruence.html
Here, I would like to add one more explanation: my represents a multiple of m, and if m=18, it will be the number 18y. The reason why I used y here is that you can basically use any variable you like as long as there are no symbols that mean the same alphabet in the formula leading up to it. For example, to put it in an extreme way, if you set 18y to 18:00 and y=hours, there is no problem as long as it is not inconvenient for you or the person being viewed.
Now, regarding Fermat's little theorem, first let's remember how to express axaxa=a^3. A is repeated three times. Fermat's little theorem means that a^(p – 1) ≡ 1 (mod p). The expression is a little difficult, so let's actually substitute numerical values. Let p=7 be a prime number. Substituting p=7 into the formula of Fermat's little theorem, we get a^(7-1) = a^6 ≡ 1 mod 7. a^6 means multiplying a six times.
As a review before this, mod 7 calculates the remainder when divided by 7, with 7 as one period. In other words, a=0,1,2,3,4,5,6 are raised as candidates, and a=7 has a remainder of 0 when divided by 7, so 7 ≡ 0 mod 7, which overlaps with a=0, so it is excluded. Masu. Negative values can also be converted to a value in the same way.
1 ^ (7 – 1) ≡ 1 ^ 6 ≡ 1 mod 7
2 ^ (7 – 1) ≡ 2 ^ 6 ≡ 64 ≡ 1 mod 7
3 ^ (7 – 1) ≡ 3 ^ 6 ≡ 729 ≡ 1 mod 7
4 ^ (7 – 1) ≡ 4 ^ 6 ≡ 4096 ≡ 1 mod 7
5 ^ (7 – 1) ≡ 5 ^ 6 ≡ 15625 ≡ 1 mod 7 6
^ (7 – 1) ≡ 6 ^ 6 ≡ 46656 ≡ 1 mod 7
One thing to note here is that a=0 is 0 no matter how many times it is multiplied by 0, so 0^(7-1)=0. Multiplying by 0 six times is still 0. In other words, if mod 7 is used, even if the number one less than that (7-1)=6 is used as an exponent, it will be 1 except for a=0.
Here, I would like to use a calculator to calculate the remainder of 109÷8. First, substitute "109", "÷", "8", and "=". "13.625" will be displayed on the calculator screen. Now subtract an integer greater than the decimal point, in this case 13. "ー" "13" "=". The screen will display "0.625", so multiply the original divided value by 8. When you press "x", "8", and "=", the desired value "5" will be displayed on the screen. This 5 is the remainder of 109÷8. When we check the calculation, we find that the calculation was correct as (109-5)÷8=13 with a remainder of 0.
Next, just to be sure, let's check whether this Fermat's little theorem is correct. The next value will be mod9.
0 ^ 8 ≡ 0 mod 9
1 ^ 8 ≡ 1 mod 9
2 ^ 8 ≡ 4 mod 9
3 ^ 8 ≡ 0 mod 9
4 ^ 8 ≡ 7 mod 9
5 ^ 8 ≡ 7 mod 9
6 ^ 8 ≡ 0 mod 9
7 ^ 8 ≡ 5 mod 9
8 ^ 8 ≡ 1 mod 9
The results of mod9 were disastrous, but in mod7, 7 was a prime number. In this case, 9 is 3×3, so it is a composite number and not a prime number. Here, mod9 has two 1s, why? First, let's check whether 9 is relatively prime. Relative prime means that the greatest common divisor is 1. In the previous Dragon Game explanation, the greatest common divisor was the overlapping part of 16=2x2x2x2 and 24=3x2x2x2. In other words, 24 and 16 have 2x2x2 in common, so the greatest common divisor is 2x2x2=8.
If I write this far and explain the combination of the linear congruence and Fermat's little theorem, it will probably become quite a long article, so I would like to touch on the relationship between disjoint and 9 that I just explained and leave it for the next article. I think. I'm probably a bit inexperienced since I've just started using Dragon Games, but I'll write one article for each keyword, and one article for the summary. Since we will be mixing two keywords this time, I think the number of articles should be 2+1. Well, let's continue.
Let's check whether the values up to 9 are prime with 9 in order.
The greatest common divisor of 9 and 1 is 3 x 3 and 1, so it becomes 1. First, the first greatest common divisor is 1, which is a relatively prime value. 9 and 2 are 3×3 and 2, so they are prime to each other. In other words, the second greatest common divisor is 1. Since 9 and 3 are 3×3 and 3, the greatest common divisor is 3 and they are not relatively prime. 4 and 5 are mutually prime★★. Since 6 is 2×3, the greatest common divisor is 3, so they are not coprime. 7 and 8 are mutually prime★★.
Therefore, the six elements that are relatively prime are 1, 2, 4, 5, 7, and 8. Here, the six numbers that are coprime to 9 are expressed as φ (pronunciation: phi) and are called Euler's phi function.
φ(9)=6.
mod7, which uses the prime number 7, is coprime other than 0, so there are 6 values where the greatest common divisor is 1. A prime number is expressed as φ(p) = p – 1.
φ(7) = 7 -1 = 6
Returning to the topic, the composite number 9, which is the product of an integer and an integer, is a ^ φ(m) ≡1 mod m, and although a and m must be relatively prime, a ^ φ(9) = a^6 =1 mod 9.
Taking 4 and 5, which were not 1, as an example, it becomes as follows.
4 ^ 6 ≡ 4096 ≡ 1 mod 9
5 ^ 6 ≡ 15625 ≡ 1 mod 9
6 ^ 6 ≡ 46656 ≡ 0 mod 9
7 ^ 6 ≡ 117649 ≡ 1 mod 9
Here, 6= 0 mod 9 because 6 and 9 are not relatively prime.
The number theory textbook I'm reading includes an explanation of Fermat's little theorem. If you want to know more, please read ``Number Theory for Beginners'' by Joseph H. Silverman.
Next time, I will synthesize the linear congruence and Fermat's little theorem, so please look forward to it. I spent a day researching a combination of these two keywords, but something happened. stay tuned. thank you for reading. See you soon.
No comments:
Post a Comment