It will NOT cover any exam or assignment related
content.
Multiplicative Inverse
Definition. If for a given integer , there exists an integer such that , we say that is invertible modulo
, and call a multiplicative
inverse of modulo .
The multiplicative inverse is NOT unique. For an
invertible , if is an inverse of , every congruent with modulo is also an inverse of . (). We use
to denote the inverse of that
.
Theorem. Let be integers,
with , and . Then is invertible modulo
if and only if is relatively prime to
. Note that integers are relatively prime (or coprime)
means .
Therefore, for a prime , every
is
invertible modulo .
The above theorem could be proved by applying Bezout's
identity: it states that for every positive integer , there exists a pair of integers
that .
Eureka moment!
逆元这个概念算是老熟人了;它将模意义下的除法转化为乘法。
求逆元的常见方法:扩展欧几里得算法,欧拉定理,费马小定理。这些方法在接下来都会进行介绍。
Euler's Totient Function
Definition. Euler's Totient Function is defined as the number of
positive integers that are relatively prime to , where is counted as being relatively prime to
all integers.
The general case of Euler's Totient is .
This is essentially the Inclusion-Exclusion
principle.
Code Implementation: Linear
Sieve
To calculate a specific totient of , we could design a trivial algorithm based on the above
formula. However, there exists a sieve algorithm that could calculate
totients of number to in linear time . Below is the code in C++:
关于欧拉函数线性筛算法的设计也十分巧妙,它是建立在质数线性筛的基础上的。具体可见
OI Wiki 中的相关解释,讲的很清楚。
Extended Euclidean Algorithm
(eGCD)
Euclidean Algorithm (辗转相除法) is one of the oldest and most widely
known algorithms. It is a
method of computing the greatest common divisor (GCD)
of two integers .
According to Bezout's Identity, there exists
integers and that given . The extended
Euclidean algorithm is the method of computing such and .
Assuming two adjacent levels in the GCD recursive process:
current
current
current
current
unknown
unknown
known
known
Therefore .
Code Implementation
1 2 3 4 5 6 7 8 9 10
intexgcd(int a, int b, int& x, int& y){ if (b == 0) { x = 1, y = 0; return a; } int gcd = exgcd(b, a % b, x, y); int _x = x; x = y, y = _x - y * a / b; // from the above equities return gcd; }
Using eGCD to get Inverse
Given , if , is invertible modulo
. We could apply eGCD algorithm to
find multiplicative inverse of modulo .
Run the above function exgcd(b,N,x,y), we could obtain
and that . Therefore . is a multiplicative inverse of modulo .
The Chinese remainder theorem (CRT) is a theorem which gives a unique
solution to a simultaneous linear congruences with coprime
moduli. In its basic form, the CRT will determine a number
that, when divided by some given
divisors, leaves given remainders.
If are
pairwise coprime, i.e., for , then the following system has exactly one solution in the sense of module for any .
We define and , then the
solution to this congruences is . Note that is unique modulo .
longlongCRT(int k, longlong* a, longlong* m){ longlong M = 1, ans = 0; for (int i = 1; i <= k; ++i) M = M * m[i]; for (int i = 1; i <= k; ++i) { longlong Mi = M / m[i], ti, _; exgcd(Mi, m[i], ti, _); // get inverse: ti * Mi mod m[i] = 1 ans = (ans + a[i] * Mi % M * ti % M) % M; } return (ans % M + M) % M; }
If there is an integer such that . We call a quadratic residue
modulo . Otherwise (such doesn't exist), we call a quadratic nonresidue
modulo .
Note that to exclude
the trivial cases .
The quadratic residue problem requires us to solve the congrence
. Essentially it
is to find the square root of in the sense of modulo . Usually, the moduli is an odd prime.
Legendre Symbol
The legendre symbol is a number theoretic function which is defined to
be equal to depending on
whether is a quadratic residue
modulo .
### Euler's Criterion
For an odd prime and , the Legendre symbol .
For an odd prime and , according to Euler's
critetion, we could determine whether is a quadratic residue modulo by checking whether equals to or not.
Group theory is the study of groups. Groups are
sets equipped with an operation that
satisfies certain basic properties. They are closure, identity, inverse,
and associativity.
Set and a
binary operation defined on that:
Closure: For all , it holds that
Identity: There exists an identity element s.t. for all
Inverse: For every element there exists an inverse element s.t.
Associativity: For all ,
Order of a finite group , denoted , is the number of elements
in .
If group is an
Abelian group, it will satisfiy the additionally
commutativity: For all , .
Subgroups
Definition. If is a
group, a set is a subgroup of if itself forms a group
under the same operation. is a strict
subgroup of if .
Note that every group
always has the trivial subgroups and .
Modulo Multiplication Group
A modulo multiplication group is a finite group of
residue classes prime to under multiplication
mod. is
Abelian of group order , where is the totient
function.
The multiplicative group of integers modulo , , is very worth
researching.
invertible elements in .
Therefore . If is prime (which is usually denoted
), .
Theorem. Let be a
finite group of order . Then for any , it holds that .
Proof. , . for all , therefore for all . With the closure
property of the group ,
is a
permutation of . Then we have , which
could be reduced to .
We could see the similarity between the proof of
Fermat's little theorem and Euler's theorem. In fact,
Fermat's little theorem is the general form of Euler's
theorem. Let be the modulo multiplication
group , one could
derive the Euler's theorem.
Corollary 1
Corollary (Fermat's Little Theorem). Let be a finite group of order
. Then for any , and any integer , we have .
Many exponents calculation could be simplified using this
corollary.
For example, if computing , we could see since . Therefore .
Corollary 2
Corollary (Fermat's Little Theorem). Let be a finite group of order
. Let be an integer, and define the
function, by .