IMO Number Theory

IMO中的数论

Theorem:

U and V co-prime if there exist intergers m, n such that

m.U + n. V = 1

Advertisements

Irrational ‘e’

April 17, 2013tomcircle Modern Math Leave a comment

In secondary school, we know how to prove √2 is irrational, how about e ?

e= 1 + 1/1! +1/2! + 1/3! + 1/4! +…

Prove by Reductio ad absurdum (contradiction):

Assume e= p/q as rational
multiply both sides by q!
LHS: e. q!= (p/q) .q! = p.(q-1)! => integer

RHS: q!+q! + (3.4…q)+ (4.5…q) +…1 + 1/(q+1) +…. => fraction

Contradiction !

Therefore e is irrational.

Number Theory is Discrete

April 11, 2013tomcircle Modern Math Leave a comment

Why Number Theory is called Discrete Math ?

because whole Number N, generator is 1, so the gap increment is 1 => discrete.

Opposite is Analysis (or Calculus), small increments ε,δ between [0,1]=> continuous, not discrete.

New branch of “Analytical Number Theory”: to prove Riemann Hypothesis.

Fermat Little Theorem

March 31, 2013tomcircle Modern Math 1 Comment

Fermat ℓittle Theorem (FℓT)

∀ m ∈ N,
1) p prime => $m^p$ = m mod (p)
Note: Converse False
[Memorize Trick: military police = military in the mode of police]
Note:
p prime, ∀m,
if p | m,
=> m ≡ 0 mod (p) …(1)
=> multiply p times:
$m^p$ ≡ 0 mod (p) …(2)

Substitute (1) to (2): m ≡ 0
=> p prime, ∀ m
$m^p$ ≡ m mod (p)
=> No need (m, p) = 1 [co-prime]

E.g. (m, p) = (3, 2) =1
$3^2$ = 9 ≡ 3 mod (2) ≡ 1 mod (2)
9 ≡ 1 mod (2)

E.g. (m, p) = (6, 2), p =2 |6
$6^2$ = 36 ≡ 6 mod (2) ≡ 0 mod (2)
6 ≡ 0 mod (2)

WRONG EXAMPLE: p = 4 = non prime
$2^4$ = 16 ≡ 2 mod (4)
but 16 ≡ 0 mod (4)
Equivalent:
p prime => $m^{p-1}$ = 1 mod (p)

by Contra-positive:
3) $m^{p-1}$ ≠ 1 mod (p)
=> p non-prime

Apply: Prove 39 non-prime?
Take m =2, p= 39
Prove $m^{p-1}$ ≠ 1 mod (p)?
a) $2^{38} =2^{36}.2^2$ .
b) $2^6$ = 64 ≡ 25 mod (39)
c) $25^2$ = 625 ≡ 1 mod (39)
From (b) & (c):

$(2^6)^6$ = $2^{36}$ ≡ $25^6$ mod(39)≡ $(25^2)^3$ ≡ $1^3$ ≡ 1
From (a): $2^{38}$ = $2^{36}.2^2$ ≡ 1×4 ≠ 1 mod(39)
=> 39 non-prime