Design and Analysis of Algorithms

650 Design and Analysis of Algorithms

B.9 NUMBER THEORY

The Chinese Remainder Theorerm There exists a number C such that

1

1

mod

mod

n

n

Cr m

Cr m

≡

≡

 

if m

i

and m

j

are relatively prime for i ≠ j.

Euler’s Function φ(x) is the number of positive integers less than x relatively prime to x.

If

1

i

n

e

i

i

p

=

∏

is the prime factorization of x then

1

1

() ( 1)

i

n

e

ii

i

xppφ

−

=

=−

∏

.

Euler’s Theorem If a and b are relatively prime then

1≡ a

φ(b)

mod b.

Fermat’s Theorem

1≡ a

p-1

mod p.

The Euclidean Algorithm If a > b are integers then

gcd(a, b) = gcd (a mod b, b).

If

1

i

n

e

i

i

p

=

∏

is the prime factorization of x then

()

1

1

1

1

i

e

n

i

i

d

|

x

i

p

Sx d

p

−

=

+

==

−

∑∏

.

Perfect Numbers x is an even perfect ...