Basics¶
This page contains pre-university level elementary results in number theory.
Definitions¶
Definition 1 (Divisibility)
For all integers \(a,b\), where \(b\neq 0\), \(b\) divides \(a\) iff there exists an integer \(n\) such that \(a=nb\).
Definition 2 (Prime Number)
For all integers \(n\geq 2\), \(n\) is prime iff it has exactly \(1\) and \(n\) itself as its positive divisors.
Definition 3 (Coprime Numbers)
For all integers \(p,q\), where \(p,q\neq 0\),
\(p\) and \(q\) are coprime iff their greatest common divisor \(\gcd(p,q)\) is \(1\).
Propositions¶
Proposition 1
For all prime numbers \(p\), \(p\) and \(p+1\) are coprime.
Proof. Take any common divisor \(d\) of \(p\) and \(p+1\). By the property of divisibility, \(d\mid p\) and \(d\mid p+1\) implies that \(d\mid (p+1)-p\) or \(d\mid 1\). Since \(d\) is a divisor of \(1\), it must be \(d=1\) only. Therefore, \(p\) and \(p+1\) are coprime.
Proof. Take the greatest common divisor \(d\) of \(p\) and \(p+1\).
Since \(d\mid p\) and \(p\) is prime, \(d\) must be either \(1\) or \(p\):
If \(d=1\), then the only common divisor of \(p\) and \(p+1\) is \(1\). Therefore, \(p\) and \(p+1\) are coprime.
If \(d=p\), then \(p\mid (p+1)\). This implies that \(p+1=pn\iff p(n-1)=1\) for some integer \(n\). However, this is impossible since \(p\) is prime and thus greater than \(1\).
Proposition 2
For all prime numbers \(p\) and integers \(a\geq 2\), \(p\) divides \(a\) iff \(p\) divides \(a^2\).
Proof. Take any prime numbers \(p\) and integers \(a\geq 2\).
To show \(\implies\), assume \(p\mid a\).
Then there exists an integer \(n\) such that \(a=np\). This implies that \(a^2=n^2p^2\), and thus \(p\mid a^2\).
To show \(\impliedby\), assume \(p\mid a^2\).
Assume for a contradiction that \(p\) does not divide \(a\), meaning \(\gcd(p,a)=1\).
By Bezout’s identity (Theorem 3), there exist integers \(x,y\) such that \(px+ay=\gcd(p,a)=1\). Multiply both sides to obtain \(apx+a^2y=a\). Since \(p\) divides the LHS, it must divide the RHS \(a\), which is a contradiction.
Lemmas¶
Lemma 1 (Euclid’s Division Lemma)
For all integers \(a,b\), where \(b\neq 0\), there exist unique integers \(q,r\) such that
\(a=bq+r\) and \(0\leq r<|b|\).
Proof. TODO
Theorems¶
Theorem 2 (Fundamental Theorem of Arithmetic)
For all integers \(n\geq 2\), there exists a unique prime factorization of \(n\).
Proof. TODO
Theorem 3 (Bezout’s Identity)
For all integers \(a,b\), there exist integers \(x,y\) such that \(ax+by=\gcd(a,b)\).
Proof. Take any integers \(a,b\).
Consider the sequence of pairs \((r_i,r_{i+1})\) defined by the Euclidean algorithm,
\(r_{-2}=q_0\cdot r_{-1}+r_0\)
\(r_{-1}=q_1\cdot r_0+r_1\)
\(r_0=q_2\cdot r_1+r_2\)
…
\(r_{n-2}=q_n\cdot r_{n-1}+r_n\)
where \(r_{-2}=a,r_{-1}=b\) and \(r_n=0\).
The proof proceeds by the (reversed) mathematical induction.
For each \(i\), we assert that there exist integers \(x,y\) such that \(r_{i-2}\cdot x+r_{i-1}\cdot y=d\), where \(d=\gcd(a,b)\).
The claim of the theorem holds by letting \(i=0\).
Base case \(i=n\):
Note that \(r_{n-1}=d\) and \(r_n=0\) by the correctness of the Euclidean algorithm.
Hence we have that \(r_{n-2}=q_n\cdot r_{n-1}+r_n\iff r_{n-2}-(q_n-1)\cdot r_{n-1}=d\),
and thus there exist integers \(x=1,y=1- q_n\) such that \(r_{-2}\cdot x+r_{-1}\cdot y=d\).
Inductive step \(i=k\):
Assume by the inductive hypothesis there exist integers \(s,t\) such that \(r_{k-2}\cdot s+r_{k-1}\cdot t=d\).
Note that \(r_{k-3}=q_{k-1}\cdot r_{k-2}+r_{k-1}\) and \(r_{k-1}\cdot t=d-r_{k-2}\cdot s\).
Hence we have \(r_{k-3}=q_{k-1}\cdot r_{k-2}+(d-r_{k-2}\cdot s)/t\).
By elementary algebra we obtain:
Hence there exist \(x=t,y=s-q_{k-1}\cdot t\) such that \(r_{k-3}\cdot x+r_{k-2}\cdot y=d\).