【数学之美 | 数论的世界】
https://m.toutiaocdn.com/group/6722962742858236429/?app=news_article_lite×tamp=1565355243&req_id=20190809205403010152022201234EA35&group_id=6722962742858236429&tt_from=android_share&utm_medium=toutiao_android&utm_campaign=client_share
(想看更多合你口味的内容,马上下载 今日头条)
http://app.toutiao.com/news_article/?utm_source=link
Tag Archives: Number Theory
RSA Encryption – Number Theory
https://dev.to/renegadecoder94/understanding-the-number-theory-behind-rsa-encryption-1pdo
Background knowledge:
1. Group
2. Cardinality : Euler Totient Function
Note:
A linguistic remark: The Latin word “totiens” (or “toties”) means “that/so many times”.
IMO Number Theory
Irrational ‘e’
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
Fermat Little Theorem
Fermat ℓittle Theorem (FℓT)
∀ m ∈ N,
1) p prime => = 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:
≡ 0 mod (p) …(2)
Substitute (1) to (2): m ≡ 0
=> p prime, ∀ m
≡ m mod (p)
=> No need (m, p) = 1 [co-prime]
E.g. (m, p) = (3, 2) =1
= 9 ≡ 3 mod (2) ≡ 1 mod (2)
9 ≡ 1 mod (2)
E.g. (m, p) = (6, 2), p =2 |6
= 36 ≡ 6 mod (2) ≡ 0 mod (2)
6 ≡ 0 mod (2)
WRONG EXAMPLE: p = 4 = non prime
= 16 ≡ 2 mod (4)
but 16 ≡ 0 mod (4)
Equivalent:
p prime => = 1 mod (p)
by Contra-positive:
3) ≠ 1 mod (p)
=> p non-prime
Apply: Prove 39 non-prime?
Take m =2, p= 39
Prove ≠ 1 mod (p)?
a) .
b) = 64 ≡ 25 mod (39)
c) = 625 ≡ 1 mod (39)
From (b) & (c):
=
≡
mod(39)≡
≡
≡ 1
From (a): =
≡ 1×4 ≠ 1 mod(39)
=> 39 non-prime