■
Linear Congruences
m: integer > 0, a and b: integers, x: variable
ax ≡ b (mod m)
となるような
をa mod mの逆元(inverse of a modulo m)という。
aとmがそれぞれ互いに素（最大公約数が１）の時、はただ１つ存在する。
例:
Find an inverse of 101 modulo 4620.
Use Euclidean algorithm to see if 101 and 4620 are prime (gcd for the numbers = 1).
By Euclidean algorithm, gcd(101, 4620) is
4620 = 45・101 + 75
101 = 1・75 + 26
75 = 2・26 + 23
26 = 1・23 + 3
23 = 7・3 + 2
3 = 1・2 + 1
2 = 2・1
Because the last nonzero remainder is 1, gcd(101, 4620) = 1.
Now find the Bezout coefficients for 101 and 4620 by working backwards.
The Bezout coefficients are -35 and 1601, and 1601 is an inverse of 101 modulo 4620.
What are the solutions of the linear congruence 3x ≡ 4 (mod 7)?
3と7はそれぞれ互いに素なので、gcd(3, 7) = 1.
3x ≡ 4 (mod 7)より、3x÷7=4になるxは、3・6÷7=4 ∴ x ＝ 6
x = 6 (mod 7), namely, 6, 13, 20, ... and -1, -8, -15, ...
中国剰余定理 The Chinese Remainder Theorem
例:
以下の連立方程式を解け。
x ≡ 2 mod 3
x ≡ 4 mod 5
解は０≦ x < 3(5)=15 の間にある。
3X + 5Y = 1を満たすX, Yをユークリッドの互除法で求める。
5 = 1・3 + 2
3 = 1・2 + 1
2 = 2・1
1 = 3 - 1(2)
= 3 - 1(5 - 1(3)) = -1(5) + 2(3)
∴ X = 2, Y = -1
= (2)(5)(-1) + (4)(3)(2) = 14
Use the method of back substitution to find all integers x such that x ≡ 1 (mod 5),
x ≡ 2 (mod 6), and x ≡ 3 (mod 7).
Use the theorem "let m be a positive integer. The integers a and b are congruent modulo m if and only if there is an integer k such that a = b + km."
By the theorem, the first congruence can be written as x = 1 + 5t, where t is an integer.
Substituting this expression for x into the second congruence, 1 + 5t ≡ 2 (mod 6).
∴ 5t ≡ 1 (mod 6)
5t (mod 6) ≡ 1 になるのは、5(5t) ≡ 5(1) (mod 6) (25 mod 6 = 1)
∴ t ≡ 5 (mod 6)
Using the theorem again, t = 5 + 6u, where u is an integer.
Substituting this expression for t back into the equation x = 1 + 5t.
x = 1 + 5t = 1 + 5(5 + 6u) = 26 + 30u.
Insert this equation into the third equation to obtain 26 + 30u ≡ 3 (mod 7).
∴ 30u ≡ -23 (mod 7) ≡ 5 (mod 7)
7 = 1(5) + 2
5 = 2(2) + 1
2 = 2(1)
gcd(5, 7) = 1, they are coprime.
1 = 5 - 2(2) = 5 - 2(7 - 1(5)) = -2(7) + 3(5)
3(30u) ≡ 3(5) (mod 7) ≡ 1 ∴ 90u ≡ 1 (mod 7)
6(90u) ≡ 6(1) (mod 7) ∴ u ≡ 6 (mod 7)
∴ u = 7v + 6, where v is an integer.
Substitutiong this expression into x = 26 + 30u = 210u +206.
∴ x ≡ 206 (mod 210)
フェルマーの小定理 Fermat's Little Theorem
例:
Find 
.
7 and 11 are coprime ⇨ 
So 
for every positive integer k.
DIvide the exponent 222 by 10, 222 = 22(10) + 2
擬素数 Pseudoprime
nを合成数、aを整数とする。合同式 
が成り立つとき、nは底aに関する擬素数(psedoprime)であるという。
例:
The integer 341 is a psedoprime to the base 2 because it is composite (341 = 11・31) and 
.
カーマイケル数 Carmichael Number
nを合成数とする。任意の整数aに対して、gcd(a, n) = 1ならば、合同式が成り立つ。この時のnをcarmichael数という。
例:
The integer 561 is a Carmichael number. To see this, first note that 561 is composite because 561 = 3(11)(17).
Next, note that if gcd(b, 561) = 1, then gcd(b, 3) = gcd(b, 11) = gcd(b, 17) = 1.
Using Fermat's little theorem we find that
擬素数かどうかはフェルマーの小定理を使って底ごとに定まるが、ある底で擬素数であっても別の底では擬素数であるとは限らないので複数の底でフェルマーの小定理を試して素数である確率を高める。
が、どんな底でも擬素数であると判定される数が存在する。これをカーマイケル数という。絶対擬素数(absolute psedoprimes)とも呼ばれる。
カーマイケル数は小さい方から561, 1105, 1729, 2465, 2821, ...で無限に存在する。
Primitive Roots and Discrete Logarithms
A primitive root modulo a prime p is an integer r in Zp such that every nonzero element of Zp is a power of r.
例:
Determine whether 2 and 3 are primitive roots modulo 11.
