Term
| Number of solutions of a linear congruence ax ≡ b (mod m) |
|
Definition
| Let d = gcd(a,m). If d does not divide b, there are no solutions. If d divides b, then there are d incongruent solutions. |
|
|
Term
|
Definition
The inverse of a modulo m is defined to be c, where ac ≡ 1 (mod m).
a only has an inverse modulo m if gcd(a,m) = 1. |
|
|
Term
| If gcd(a,c)=1 and gcd(b,c)=1, then... |
|
Definition
|
|
Term
| Chinese Remainder Theorem |
|
Definition
Assume that m_1, ..., m_k are pairwise relatively prime. Define M = m_1 * ... * m_k. Then the system of congruences
x ≡ a_1 (mod m_1)
x ≡ a_2 (mod m_2)
...
x ≡ a_k (mod m_k)
has a unique solution modulo M, namely
x_0 = sum from i=1 to k of a_i M_i y_i
where M_i = M / m_i and
y_i is the inverse of M_i modulo m_i. |
|
|
Term
|
Definition
| If p is prime, then (p-1)! ≡ -1 (mod p) |
|
|
Term
|
Definition
If p is prime and a is an integer such that p does not divide a, then
a^(p-1) ≡ 1 (mod p)
Equivalently, a^p ≡ a (mod p) |
|
|
Term
|
Definition
phi(n) is the number of natural numbers coprime to n that are less than or equal to n.
If n is prime, phi(n) = n-1.
The Euler-phi function is multiplicative! |
|
|
Term
| Reduced residue system modulo m |
|
Definition
A set S contained in Z is a reduced residue system modulo m if the following hold.
(1) |S| = phi(n),
(2) gcd(x,n)=1 for all x in S,
(3) x is incongruent to y for all distinct x, y in S. |
|
|
Term
|
Definition
Let m be a natural number and a be an integer such that gcd(a,m)=1. Then
a^(phi(m)) ≡ 1 (mod m) |
|
|
Term
| How to use Euler's theorem to find the inverse of a modulo m |
|
Definition
| An inverse of a modulo m is a^(phi(m)-1) provided that gcd(a,m)=1. |
|
|
Term
| gcd(a,b)=1 if and only if... |
|
Definition
| ...a and b do not have a common prime divisor. |
|
|
Term
|
Definition
| A function is called arithmetic if it is defined for all natural numbers. |
|
|
Term
|
Definition
| An arithmetic function f is multiplicative if f(mn) = f(m)f(n) for all coprime integers m, n. |
|
|
Term
| Let p be prime and let a be a natural number. Then phi(p^a) = ? |
|
Definition
|
|
Term
| If a ≡ b (mod n), then what can we say about the greatest common divisors of a, b, and n? |
|
Definition
|
|
Term
| Explicit formula for phi(n) |
|
Definition
| phi(n) = n * product over all prime divisors p of n of (1 - 1/p) |
|
|
Term
|
Definition
|
|
Term
|
Definition
Let f be an arithmetic function. The summatory function of f is defined to be
F = sum over all divisors d of n of f(d) |
|
|
Term
| The summatory function of phi(n)... |
|
Definition
| ...is the identity mapping on the natural numbers, eta(n) = n. |
|
|
Term
| Number of divisors function |
|
Definition
tau(n) = the number of divisors of n.
tau = nu * nu |
|
|
Term
|
Definition
sigma(n) = the sum of all divisors of n.
sigma = nu * eta |
|
|
Term
| Multiplicity of summatory functions |
|
Definition
| The summatory function of any multiplicative function is also multiplicative. |
|
|
Term
Let p be prime and a be a natural number.
tau(p^a) = ? |
|
Definition
|
|
Term
Let p be a prime and a be a natural number.
sigma(p^a) = ? |
|
Definition
sigma(p^a) = 1 + p + ... + p^a
= [p^(a+1) - 1]/[p - 1] |
|
|
Term
| tau(n) in terms of the prime factorization of n |
|
Definition
Let n = p_1^(a_1) ... p_k^(a_k).
tau(n) = (a_1 + 1)...(a_k + 1) |
|
|
Term
| sigma(n) in terms of the prime factorization of n |
|
Definition
Let n = p_1^(a_1) ... p_k^(a_k)
sigma(n) = product from j=1 to k of [p_j^(a_j + 1) - 1]/[p_j - 1] |
|
|
Term
|
Definition
mu(n) =
1, if n = 1,
(-1)^s, if n is a product of s distinct primes,
0, otherwise. |
|
|
Term
|
Definition
Assume f is an arithmetic function with summatory function F. Then
f(n) = sum over all divisors d of n of mu(d) F(n/d) |
|
|
Term
|
Definition
If f, g are arithmetic functions,
(f*g)(n) = sum over all divisors d of n of f(d) g(n/d) |
|
|
Term
| Identity element under the Dirichlet product |
|
Definition
iota(n) =
1, if n = 1,
0, if n > 1.
iota * f = f * iota = f, for all f. |
|
|
Term
| Inverse of the Mobius function |
|
Definition
The inverse of mu is nu, where nu(n) = 1 for all n.
mu * nu = nu * mu = iota |
|
|
Term
| Euler-phi function as a Dirichlet product |
|
Definition
|
|
Term
| If n is a natural number greater than 1, only one of the following can be true... |
|
Definition
(1) n is a product of distinct primes
(2) n is not square-free |
|
|
