Number Theory

Combinatorics

1
Outline
 Number Theory
 Prime Number
 Congruences
 Fermat’s Theorem
 Euler’s Theorem

2
Number Theory
 Number theory is concerned with properties of integers.
 It is perhaps the most interesting and beautiful area of
mathematics.
 Number theory plays an important role in modern cryptography.
 Some outstanding unsolved problems:
 Goldbach’s Conjecture: every even integer n > 2 is the sum of 2
primes.
 Twin Prime Conjecture: There are infinitely many twin primes. (If
p and p+2 are primes, we say p and p+2 are twin primes.)
 Are there infinitely many primes of the form n2 + 1? How about
the form 2n -1?

3
Numbers
 Natural numbers: N = {1, 2, 3,…}
 Integers: Z = {…, -2, -1, 0, 1, 2, … }
 Rational numbers: Q={n/m | m≠0}
 Real numbers: R

4
Number Base Conversion
 How to convert a decimal number to another
base b?
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
int d, b, t, r;
vector<int> v;
cin >> d >> b;
while (d > 0) {
r = d % b;
v.push_back(r);
d = d/b;
}
reverse(v.begin(), v.end());
for (int i = 0; i < v.size(); ++i)
cout << v[i];
cout << endl;
return 1;
5
}
Divisibility
 d | n means there is an integer k such that n
= d·k.
 d | n has several readings:
 d divides n
 d is a divisor of n
 d is a factor of n
 n is a multiple of d

6
Divisibility Properties
 n | n, and 1 | n
 d | n and n | m  d | m
 d | n and d | m  d | an + bm for all a and b
 d | n  ad | an
 d|0
 If d and n are positive and d | n, then d ≤ n.
 If d | n, then n/d | n, and
 small(d, n/d) <= sqrt(n)
7
The Division Algorithm
 If a and b are integers and b > 0, then there
exist unique integers q and r satisfying the
two conditions:
 a = bq + r, and
 0≤r<b
 For b > 0, define a mod b = r where r is the
remainder given by the division algorithm
when a is divided by b, that is, a = bq + r and
0 ≤ r < b.
8
Prime Numbers
 A prime number is an integer >1 and only has
divisors of 1 and itself
 It cannot be written as a product of other numbers
 E.g. 2,3,5,7 are prime, 4,6,8,9,10 are not
 prime numbers are central to number theory
 list of prime number less than 200 is:
2 3 5 7 11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89 97 101
103 107 109 113 127 131 137 139 149 151
157 163 167 173 179 181 191 193 197 199
9
Primality Testing
 We often need to find large prime numbers
 Traditionally we can use trial division
 i.e. divide by all numbers (primes) in turn, less than the
square root of the number
 only works for small numbers
 Alternatively, we can use statistical primality tests
based on properties of primes
 for which all primes numbers satisfy property
 but some composite numbers, called pseudo-primes, also
satisfy the property

10
Trial division
int is_prime(int n) {
if (n <= 1) return 0;
if (n == 2) return 1; // 2 is a prime
if (n%2 == 0) return 0; // NO prime is EVEN, except 2
for (int i = 3; i * i <= n; i += 2) // start from 3, jump 2 numbers
if (n%i == 0) // no need to check even numbers
return 0;
return 1;
}

11
Divisibility check using smaller
primes below sqrt(N)
 number N is a prime if and only if no primes below sqrt(N) can
divide N
 Generate a prime table
 Suppose max primes generated will not be greater than 2^31-1
(2,147,483,647).
 We need smaller primes below sqrt(N), so we need to store primes no
greater that sqrt(2^31-1)
 sqrt(2^31) = 46340.95
 There will be at most 4792 primes in the range 1 to 46340.95
 We only need about array of size (roughly) 4800 elements
 check whether a big number N is a prime or not by dividing it
with small primes up to sqrt(N)
 If you can find at least one small primes that can divide N, then N
is not prime, otherwise N is prime

12
Prime Table Generation (I)
bool isPrime[MAXN];
int i, tot, prime[];
memset(isPrime, true, sizeof(isPrime));
tot = 0;
prime[tot++] = 2;
for ( i = 3; i < MAXN; i+=2) {
if (isPrime[i])
prime[tot++] = i;
for(j = i + i; j < MAXN; j+=i)
isPrime[j] = false;
}
}
13
Prime Table Generation (II)
bool isPrime[MAXN];
int i, tot, prime[];
memset(isPrime, true, sizeof(isPrime));
tot = 0;
for ( i = 2; i <= n; i++) {
if (isPrime[i])
prime[tot++] = i;
for (j = 0; j < tot && i * prime[j] <= n; j++) {
isPrime[i*prime[j]] = false;
if (i % prime[j] == 0)
break;
}
}

14
Prime Distribution
 There are an infinite number of primes.
 Can you prove it?
 Let π(x) denote the number of primes p such that p
≤ x.
 Prime number theorem states that primes occur
roughly every ln(n) integers:
 π(x) ~ x/ln(x) for all x > 0.
 Since we can immediately ignore evens and
multiples of 5, in practice we only need to test
0.4ln(n) numbers of size n before finding a prime
15
Prime Factorization
 to factor a number n is to write it as a
product of other numbers: n=a × b × c
 note that factoring a number is relatively hard
compared to multiplying the factors together
to generate the number
 the prime factorisation of a number n is
when its written as a product of primes
 E.g. 91=7×13 ; 3600=24×32×52

16
Number of divisors
 If the prime factorisation of a number n is

 Then the number of positive divisors of n is

17
Relatively Prime Numbers & GCD
 two numbers a, b are relatively prime if they
have no common divisors apart from 1
 E.g. 8 & 15 are relatively prime since factors of 8
are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the
only common factor
 We can determine the greatest common
divisor by comparing their prime
factorizations and using least powers
 E.g. 300=21×31×52 18=21×32 hence
GCD(18,300)=21×31×50=6
18
GCD: Euclid’s algorithm
 Two observations:
 If b|a, then gcd(a,b) = b
 If a = bt + r, then gcd(a,b) = gcd(b, r)
 Euclid’s algorithm is recursive, repeated
replacing the bigger integer by its remainder
mod the smaller integer.
 E.g.: a = 34398, b = 2132
gcd(34398, 2132) = gcd(34398 mod 2132, 2132) = gcd(2132, 286)
= gcd(2132 mod 286, 286) = gcd(286, 130)
= gcd(286 mod 130, 130) = gcd(130, 26)
= gcd(130 mod 26, 26) = gcd(26, 0)
= 26 19
Big Modular
 How to calculate A1A2…An mod p?
 The product may be very large and overflow!
 It can be calculated by:
 (A1 mod p) x (A2 mod p) x … (An mod p)
 Another example: how to calculate bp mod m?
long bigmod(long b, long p, long m) {
if (p == 0)
return 1;
else if (p%2 == 0)
return square(bigmod(b, p/2, m)) % m; // square(x) = x * x
else
return ((b % m) * bigmod(b, p-1, m)) % m;
}
20
Sample Code
//Greatest Common Divisor
int gcd(int a, int b) {

for(i=2;i<=smallb;i++)
{
if(a%i==0 && b%i==0)
{
store=i;
}
}
Return store;
}

// Lowest Common Multiple

}
Congruences
 We say that a≡b (mod m) if m|(a-b).
 Congruences are an alternate notation for modular
arithmetic.
 Addition: Suppose a≡b (mod n) and c≡d (mod n), then
a+c≡b+d (mod n)
 Multiplication: If a≡b (mod n), then a·d≡b·d (mod n).
 Exponentiation: If a≡b (mod n), then am≡bm (mod n)
 Division??? 6·2≡6·1 (mod 3), but…

22
Congruences
 Theorem 1: Let m ≥ 2. If a and m are
relatively prime, there exists a unique integer
a* such that aa* ≡ 1 (mod m) and 0 < a* < m.
 We call a* the inverse of a modulo m.
 Theorem 2: Let m > 0. If ab ≡ 1 (mod m), then
both a and b are relatively prime to m.
 Theorem 3: Let m > 0 and assume
gcd(c,m)=1. Then ca ≡ cb (mod m)  a ≡ b
(mod m).
23
Fermat's Little Theorem
 If p is prime and gcd(a, p) = 1, then
 ap-1 mod p = 1
 E.g., how to calculate 12347865435 mod 11?
 1234 ≡ 2 (mod 11)  12347865435 ≡ 2 7865435 (mod 11)
 210 ≡ 1 (mod 11) (according to Fermat’s litter theorem)
 2 7865435 ≡ 2786543x10+5 (mod 11)
≡ (2^10)786543 x 25 (mod 11)
≡ 1786543x 25 (mod 11)
≡ 25 (mod 11)
≡ 10 (mod 11)
 So 12347865435 mod 11 = 10.

24
Euler Totient Function ø(n)
 when doing arithmetic modulo n
 complete set of residues is: 0..n-1
 reduced set of residues is those numbers
(residues) which are relatively prime to n
 E.g. for n=10,
 complete set of residues is {0,1,2,3,4,5,6,7,8,9}
 reduced set of residues is {1,3,7,9}
 number of elements in reduced set of residues is
called the Euler Totient Function ø(n)

25
Euler Totient Function ø(n)
 To compute ø(n), we need to count number
of elements to be excluded
 in general, it needs prime factorization, but
 for p (p prime) ø(p) = p-1
 for p.q (p,q prime) ø(p·q) = (p-1)(q-1)
 E.g.
 ø(37) = 36
 ø(21) = (3–1)×(7–1) = 2×6 = 12

26
Euler's Theorem
 aø(n) mod n = 1
 where gcd(a, n)=1
 It is a generalisation of Fermat's Theorem
 E.g.
 a=3;n=10; ø(10)=4;
 hence 34 = 81 = 1 mod 10
 a=2;n=11; ø(11)=10;
 hence 210 = 1024 = 1 mod 11

27