Term
|
Definition
φ(n)=|{x∈ℤ:1≤x≤n;(x,n)=1}|
In other words, φ(n) is the number of positive integers less than or equal to n that are relatively prime to n. Note that n will be relatively prime to itself iff n=1
Examples:
φ(12)=4 (1,5,7,11)
φ(14)=6 (1,3,5,9,11,13)
φ(p)=p-1 |
|
|
Term
|
Definition
Let a,m∈ℤ with m>0. If (a,m)=1, then,
aφ(m)≡1 mod m |
|
|
Term
| Euler's Relationship to Fermat's Little Thm |
|
Definition
| Fermat's Little thm follows from Euler's by taking m to be a prime number (φ(p)=p-1). Fermat's is a special case of Euler's |
|
|
Term
| Def: Reduced Residue System Modulo m |
|
Definition
Let m be a positive integer. A set of φ(m) integers s.t. each element of the set is relatively prime to m and no two elements of the set are congruent modulo m is said to be a reduced residue system modulo m.
A reduced res. sys. mod 12 is given by the set {1,5,7,11}
A reduced res. sys. mod 14 is given by the set {1,3,5,9,11,13}
A reduced res. sys. mod p is given by the set {1,2,...,p-1}
Equivalently, a reduced
residue system modulo m is the subset of a complete residue system consisting of those elements that are relatively prime with m |
|
|
Term
| Prop: If {r1,r2,...,rφ(m} is a reduced residue system modulo m, |
|
Definition
| then so is the
set {ar1,ar2,...,arφ(m} for any integer a with (a,m)=1. |
|
|
Term
| Corollary: inverse of a mod m |
|
Definition
| Let a,m∈ℤ with m>0. If (a,m)=1, then aφ(m)-1 is the inverse of a modulo m |
|
|
Term
|
Definition
An arithmetic function is a function whose domain is the set of positive integers.
φ(n)
ν(n)
σ(n) |
|
|
Term
|
Definition
An arithmetic function f is said to be multiplicative if f(mn)=f(m)f(n) whenever m and n are relatively prime ((m,n)=1)
An arithmetic function f is said to be completely multiplicative if f(mn)=f(m)f(n) for all positive integers m and n
Note: n=p1α1p2α2...prαr with p1,p2,...,pr distinct prime numbers. (piαipjαj)=1, thus
f(n)=f(p1α1p2α2...prαr)=f(p1α1)f(p2α2)...f(prαr)
In other words, a multiplicative arithmetic function is completely determined by its values at powers of prime numbers. |
|
|
Term
| Some notational conventions |
|
Definition
∑d∣n f(d) denotes a sum of f(d), taken over all positive divisors d of n.
∑p∣n f(p) denotes a sum of f(p), taken over all prime divisors p of n.
∑pα||n f(pα) denotes a sum of f(pα), taken over all prime powers pα that occur in the standard prime factorization of n. (Here the double bar in pα||n indicates that pα is the exact power of p dividing n, i.e., pα∣n but pα+1∤n) |
|
|
Term
| Empty sum/product convention |
|
Definition
| A sum over an empty set is defined to be 0; a product over an empty set is defined to be 1. |
|
|
Term
| Properties of the Euler phi-function |
|
Definition
i) The Euler phi-function is multiplicative (though not completely)
ii)(Explicit Formula) For any n∈ℕ,
φ(n)=∏pα||n pα-1(p-1)=n∏p∣n (1-(1/p))
For p prime and α a positive integer, φ(pα)=pα-pα-1
iii) (Gauss id) ∑d∣n φ(d)=n
Example: φ(504)
504=23327
φ(504)=504(1-(1/2))(1-(1/3))(1-(1/7))
=504(1/2)(2/3)(6/7)
=144
There are exactly 144 positive integers not exceeding 504 that are relatively prime to 504. |
|
|
Term
|
Definition
| Given n∈ℕ, the equation φ(x)=n has either no solution x∈ℕ or more than one solution |
|
|
Term
| Def: Number-of-divisors function, ν(n) |
|
Definition
Let n∈ℕ. The number of postive divisors function is
ν(n)=|{d∈ℕ;d∣n}|
In other words, ν(n) is the number of positive divisors of n.
Note that ν(n)=∑d∣n1 |
|
|
Term
|
Definition
i) The function ν(n) is multiplicative (though not completely)
ii) (Explicit formula) For any n∈ℕ,
ν(n)=∏pα||n (α+1)
For p prime, ν(pα)=α+1
Example ν(504)
504=23327
ν(504)=(3+1)(2+1)(1+1)
=24
There are exactly 24 positive divisors of 504 |
|
|
Term
| Def: The sum-of-divisors function, σ(n) |
|
Definition
Let n∈ℕ. The sum of postive divisors function is
σ(n)=∑d∣n d
In other words, σ(n) is the sum of the positive diviors of n |
|
|
Term
|
Definition
i) The function σ(n) is multiplicative (though no completely)
ii)(Explicit formula) For any n∈ℕ,
σ(n)=∏pα||n (p(α+1)-1)/(p-1)
For p prime, σ(pα)=(pα+1-1)/(p-1)
Example: σ(504)
504=23327
σ(504)=((24-1)/(2-1))((33-1)/(3-1))((72-1)/(7-1))
=1560
1560 is the sum of the positive divisors of 504 |
|
|
Term
|
Definition
Let n∈ℕ. Then n is said to be a perfect number if σ(n)=2n
Equivalently, n is said to be a perfect number if σ(n)-n=n. ie if the sum of all positive divisors of n other than n itself is equal to n
Examples:
6 is a perfect number since σ(6)=12=2(6) |
|
|
Term
| Thm: Characterization of even perfect numbers |
|
Definition
Let n∈ℕ. Then n is an even perfect number iff
n=2p-1(2p-1), where 2p-1 is a Mersenne prime. |
|
|
Term
| Corollary about Perfect numbers |
|
Definition
| There exist infinitely many even perfect number iff there exist inf many Mersenne primes. |
|
|
Term
| Conjectures about perfect numbers |
|
Definition
1. There are inf many perfect primes
2. Every perfect number is even. |
|
|
Term
| Def: Möbius μ-function, μ(n) |
|
Definition
Let n∈ℕ. The Möbius μ-function is
μ(n)=
1 if n=1
(-1)r if n=p1p2...pr with distinct primes p
0 if n is not square free, i.e. divisible by a prime power pα with α>1
Examples
a) Since 504=23327, we have that two squares of prime numbers divide 504 so μ(504)=0
b) Since 30=2(3)(5), we have that 30 is a product of three distinct square free prime numbers so μ(30)=(-1)3=-1 |
|
|
Term
|
Definition
i) The Möbius μ-function is multiplicative (though not completely)
ii) (Möbius function id)
∑d∣n μ(d)=
Example
Let n=12. Then
∑d∣12 μ(d)=μ(1)+μ(2)+μ(3)+μ(4)+μ(6)+μ(12)
=1+(-1)+(-1)+0+1+0
=0 as desired since 12=223 |
|
|
Term
| Thm: Möbius Inversion Formula |
|
Definition
Let f and g be arithmetic function. Then
f(n)= ∑d∣ng(d)
iff
g(n)=∑d∣nμ(d)f(n/d)=∑d∣nμ(n/d)f(d)
Examples on pg 99 |
|
|
Term
| Def: Trivial arithmetic function |
|
Definition
The unit function 1, identity function id, and delta function δ are the arithmetic functions defined as follows:
1(n)=1
id(n)=n
δ(n)=1 if n=1, 0 o/w
All three are completely multiplicative |
|
|
Term
| Def: Dirichlet product of arithmetic functions |
|
Definition
Given two arithmetic functions f and g, the Dirichlet product f*g is the arithmetic function defined by
(f*g)(n)=∑d∣nf(d)g(n/d) |
|
|
Term
| Alg properities of Dirichlet product |
|
Definition
Let f,g,h be arithmetic functions.
(commutativity) f*g=g*f
(associativity) (f*g)*h=f*(g*h)
(identity element)f*δ=δ*f=f, where δ is defined as δ(1)=0, δ(n)=0
(Dirichlet inverse) If f(1)≠0, then f has a unique Dirichlet inverse f*-1, in the sense that f*f*-1=δ
(preservation of multiplicativity) The Dirichlet product of two mult. fuctions is mult.
(Mult. of inverse) The Dirichlet inverse of a mult. function is mult.
|
|
|
Term
| Dirichlet Product versions of identities for arithmetic functions |
|
Definition
(Guass) φ*1=id
(Def of the divisor function) ν=1*1
(Def of the sum of divisors function) σ=1*id
(Möbius function identity) μ*1=δ
(Möbius inversion formula) If f=g*1, then g=f*μ=μ*f
|
|
|
Term
| Def: Quadratic residue modulo m |
|
Definition
Let a,m∈ℤ with m>0 and (a,m)=1. Then a is said to be a quadratic residue modulo m if the quadratic congruence x2≡a mod m is solvable in ℤ; o/w, a is said to be a quadratic nonresidue modulo m.
0 is neither a quad res nor nonres. |
|
|
Term
| Prop: Number of solutions to quad. congruences |
|
Definition
| Let p be an odd prime number and let a∈ℤ with p∤a. Then the quad. congr. x2≡a mod p has either no solutions (nonresidue) or exactly two incongruent solutions modulo p (residue). More precisely, if x0 is one solution, then a second, incongruent solution is p-x0 |
|
|
Term
| Prop: More on number of quad congr. |
|
Definition
| Let p be an odd prime number. Then there are exactly (p-1)/2 incongruent quadratic residues modulo p and exactly (p-1)/2 incongruent quad. nonres. modulo p |
|
|
Term
|
Definition
Let p be an odd prime number and let a∈ℤ with p∤a. The Legendre symbol is
(a/p)=
1, if a is a quadratic res. mod p
-1, if a is a quad. nonres. mod p
In other words, the Legendre symbol records whether the quad congruence x2≡a mod p is solvable |
|
|
Term
|
Definition
Let p be an odd prime number and let a∈ℤ with p∤a, ie (a,p)=1. Then
(a/p)=a(p-1)/2 mod p |
|
|
Term
| Prop 4.5: Properties of the Legendre Symbol |
|
Definition
Let p be an odd prime, and let a,b∈ℤ with (a,p)=1 and (b,p)=1.
i) (Periodicity in numerator) If a≡b mod p, the (a/p)=(b/p)
ii) (Complete mult in num) (ab/p)=(a/p)(b/p)
iii) (Value at squares) (a2/p)=1 |
|
|
Term
|
Definition
Let p be an odd prime number. Then
(-1/p)=
1, if p≡1 mod 4
-1, if p≡3 mod 4 |
|
|
Term
|
Definition
Let p be an odd prime number. Then
(2/p)=
1, if p≡1,7 mod 8
-1, if p≡3,5 mod 8 |
|
|
Term
| Thm: Law of Quadratic Reciprocity |
|
Definition
Let p and q be distinct odd prime numbers. Then
(p/q)(q/p)=
1, if p≡1 mod 4 or q≡1 mod 4 (or both
-1, if p≡q≡3 mod 4
Equivalently, (p/q)=
-(q/p) if p≡3 mod 4 AND q≡3 mod 4
(q/p) o/w |
|
|
Term
|
Definition
Let m∈ℕ and a∈ℤ s.t. (a,m)=1. The order of a modulo m, denoted ordma, is the least positive integer k s.t.
ak≡1 mod m
By Euler's Thm, a k is guarenteed so the order is well-defined and is at most equal to φ(m) |
|
|
Term
| Prop 5.2: Properties of an order |
|
Definition
Let m∈ℕ and a∈ℤ s.t. (a,m)=1, and let ordma be the order of a modulo m. Then:
i) (Periodicity) If b≡a mod m, then ordmb= ordma
ii) (Relation to Euler phi) ordma∣φ(m)
iii) (Characterization of "good" exponents) The set of positive integers k for which the congruence ak≡1 mod m
holds consists exactly of the positive integer multiples of ordma
iv) (Order of powers of a) For any positive integer i,
ordmai=ordma/(ordma,i)
In particular, ordmai=ordma iff (ordma,i)=1 |
|
|
Term
| Prob: Number of elements of given order |
|
Definition
| Let p be an odd prime. Then the possible orders of integers mod p are exactly the positive divisors of p-1=φ(p). Moreover, given any positive divisor d∣p-1, there exist exactly φ(d) incongruent integers a with ordpa=d |
|
|
Term
|
Definition
| Let m∈ℕ and a∈ℤ s.t. (a,m)=1. Then a is called a primitive root modulo m if ordma=φ(m), ie, if the order of a is equal to the maximal possible value |
|
|
Term
| Prop: Primitive roots and reduced systems of residues |
|
Definition
Let m∈ℕ, and suppose r is a primitive root mod m. Then the set
{r, r2,..., rφ(m)}
is a system of reduced residues mod m. That is, the elements in this set are pairwise incongruent mod m, and every integer a with (a,m)=1 is congruent mod m to an element in the above set. |
|
|
Term
| Thm: Existence of Primitive Roots (Prim. Root Thm) |
|
Definition
Let m be a positive integer. Then there exists a primitive root mod m iff m has one of the following forms:
i) m=pα, where p is an odd prime and α∈ℕ,
ii) m=2pα, where p is an odd prime and α∈ℕ,
iii) m=1,2,4 |
|
|
Term
| Thm: Number of primitive roots |
|
Definition
| Let m be of one of the forms of the Primitive Root Thm, so that there exists at least one primitive root mod m. Then there exists exactly φ(φ(m)) incongruent primitive roots modulo m |
|
|
