number theory

divides

an integer \( n \) is divisible by a non-zero integer \( m \) if there exists an integer \( k \) such that \( n = k \cdot m \). If this is all true we write \( m | n \).

1 divides everything

Suppose that \( j \in \mathbb{Z} \), then \( 1 | j \)

In the definition of divides take \( k = j \), then we can see that \( j = j \cdot 1 \) thus we can say that \( 1 | j \)

0 is divisible by everything

for any \( d \in \mathbb{Z}^{\ne 0} , d | 0 \)

In the definition of divides take \( k = 0 \), then we can see that \( 0 = 0 \cdot d \) thus we can say that \( d | 0 \)

any integer cannot divide something smaller than itself

Suppose that \( m \in \mathbb{Z} \), then for any \( a \in \mathbb{Z}^{\ne 0} \) such that \( - \left | m \right | < a < \left | m \right | \), then \( m \) does not divide \( a \)

Suppose that for the sake of contradiciton that \( m | a \) , then there is some \( k \in \mathbb{Z} \) such that \( a = m k \)

forced division of sum

Suppose that \( m | a \) and that \( m | \left ( a + b \right ) \) then \( m | b \)

TODO

even number

Given an integer \( a \), we say that it is even when \( 2 | a \)

quotient remainder

Suppose that \( a , b \in \mathbb{Z} \), but that \( b \ne 0 \), then there exists unique integers \( q , r \) such that \( a = b \cdot q + r \) where \( 0 \le r \lt \left | b \right | \)

Let \( a , b \in \mathbb{Z} \) and assume \( b \ne 0 \). Define \( S = \left \lbrace x \in \mathbb{Z} : x \ge 0 \text{ and } x = a + \left | b \right | \cdot k \text{ where } k \in \mathbb{Z} \right \rbrace \supseteq \mathbb{N}_{0} \), we'll show that \( S \) is non-empty. We can think of \( S \) as taking \( a \) and then either adding muliples of \( \left | b \right | \) or subtracting them to \( a \), each time leaving some remainder, thinking ahead we can guess that the smallest value of this set should be the smallest remainder and possibly the \( r \) we are looking for.

If \( a \ge 0 \) then when \( k = 0 \) we have \( a + \left | b \right | \cdot k = a \ge 0 \) thus \( a \in S \), on the other hand if \( a \lt 0 \), then observe that since \( 0 \le r \lt \left | b \right | \), then \( 1 \le \left | b \right | \iff 0 \le \left | b \right | - 1 \) and also \( - a \gt 0 \), then we have \( 0 \le \left ( \left | b \right | - 1 \right ) \cdot \left ( - a \right ) \). But also we can see that \( \left ( \left | b \right | - 1 \right ) \cdot \left ( - a \right ) = \left | b \right | \cdot \left ( - a \right ) + a \) so it's of the form of an element in \( S \) and since it's non-negative, it must be an element of \( S \). Therefore this paragraph shows us that \( S \) has at least one element, no matter the value of \( a \).

Due to this and since \( S \subseteq \mathbb{N}_{0} \), then by the well ordering principle there is some smallest element \( s \in S \), we know that this value satisfies \( s = a - \left | b \right | \cdot k \). Now we will show that \( 0 \le s \lt \left | b \right | \).

At this point we have \( a = \left | b \right | \cdot k + s \) where \( 0 \le s \lt \left | b \right | \) so take \( q = \text{sgn} \left ( b \right ) \cdot k \) and \( r = s \). If \( b \ge 0 \), then \( \left | b \right | = b \) and \( \text{sgn} \left ( b \right ) = 1 \), so we obtain \( a = b \cdot k + s \), if \( b < 0 \), then \( \left | b \right | = - b \) and \( \text{sgn} \left ( b \right ) = - 1 \) so again we have \( a = \left ( - b \right ) \cdot \left ( - 1 \right ) k + s \). We'll finish the proof by showing that these values are unique.

Assume we have another pair \( \overline{q} , \overline{r} \) satisfying \( a = b \cdot \overline{q} + \overline{r} \) with \( 0 \le \overline{r} \le \left | b \right | \) but \( \overline{q} \ne q \) and \( \overline{r} \ne r \), therefore we have \( b \cdot q + r = b \overline{q} + \overline{r} \iff \overline{r} - r = b \cdot \left ( \overline{q} - q \right ) \).

Without loss of generality assume \( \overline{r} \gt r \), then \( \overline{r} - r \gt 0 \) and since \( 0 \le r \lt \left | b \right | \) then \( 0 \le \overline{r} - r \le \overline{r} \lt \left | b \right | \), recalling that \( \overline{r} - r = \left | b \right | \cdot \left ( \overline{q} - q \right ) \), we can re-write our last inequality as \( 0 \le \left | b \right | \cdot \left ( \overline{q} - q \right ) \lt \left | b \right | \) and since \( b \ne 0 \) we can divide by \( \left | b \right | \) to get \( 0 \lt \overline{q} - q \lt 1 \) but since \( q , \overline{q} \in \mathbb{Z} \) this force \( q = \overline{q} \), which then shows \( r = \overline{r} \) by previous equalities, therefore assuming we have another solution, it turns out it must be our original one, and thus our solution is unique.

remainder function

Given two integers \( a , b \in \mathbb{Z} \) such that \( b \ne 0 \), then we get some \( q , r \in \mathbb{Z} \) with \( 0 \le r \lt \left | b \right | \) such that \( a = b \cdot q + r \) and we define \( a \% b := r \)

divisor function

quotient remainder on positive integer has positive divisor

Suppose that \( a , b \in \mathbb{N}_{1} \) such that \( a \ge b \) then \( a / / b \ge 1 \)

For brevity define \( q = a / / b \), we know that \( a = b \cdot q + r \) with \( 0 \le r \lt b \), thus far we know that \( q \in \mathbb{Z} \), though if \( q < 0 \), then we know that \( b \cdot q < r \cdot q \le 0 \), therefore \( a = b \cdot q + r < r \cdot q + r = r \left ( q + 1 \right ) \)

For a contradiction assume that \( q \lt 1 \iff q \le 0 \), therefore \( r \left ( q + 1 \right ) \le r \left ( 0 + 1 \right ) = r \), which shows that \( a \lt r \), since \( 0 \le r \lt b \), then we have \( a \lt b \) which is a contradiction because we know that \( a \ge b \).

Since by assuming \( q \lt 1 \), we have a contradiction, so therefore \( q \ge 1 \), which is the same as \( a / / b \ge 1 \).

every integer is either odd or even

For any \( z \in \mathbb{Z} \), it is even or it is odd

Let \( z \in \mathbb{Z} \) and then we know that \( z \% 2 \in \left \lbrace 0 , 1 \right \rbrace \), if \( z \% 2 = 1 \) then there is some \( q \in \mathbb{Z} \) such that \( z = q \cdot 2 + 1 \), and thus odd, if \( z \% 2 = 0 \), then we have some \( q \in \mathbb{Z} \) such that \( z = q \cdot 2 + 0 \) and is thus even.

composite number

A number \( n \in \mathbb{N}_{1} \) is said to be composite, when it has a positive divisor other than \( 1 \) and itself

prime

A number \( p \in \mathbb{N}_{1} \) is said to be prime if it's only divisors are \( 1 \) and \( p \)

greatest common divisor

suppose that \( a , b \in \mathbb{Z} \) then the greatest common divsor of \( a \) and \( b \) notated as \( \gcd{\left ( a , b \right )} \) is the largest positive integer that divides each of \( a , b \)

same divisors implies same gcd

Suppose that \( a , b , p , q \in \mathbb{Z} \) and that \( D_{a , b} = \left \lbrace d \in \mathbb{Z} : d \left \lvert a \text{ and } d \mid b \right \rbrace \right. \) and \( D_{p , q} = \left \lbrace d \in \mathbb{Z} : d \left \lvert p \text{ and } d \mid q \right \rbrace \right. \) are equal, then \( \gcd{\left ( a , b \right )} = \gcd{\left ( p , q \right )} \)

TODO

coprime integers

\( a , b \in \mathbb{Z} \) are said to be coprime if the only positive integer that divides them is \( 1 \).

\( a , b \in \mathbb{Z} \) are coprime if and only if \( \gcd{\left ( a , b \right )} = 1 \)

TODO

euclidean algorithm

Let \( m , n \in \mathbb{N}_{1} \) such that \( m > n \), if \( m \% n > 0 \), then \( \gcd{\left ( m , n \right )} = \gcd{\left ( n , m \% n \right )} \). Otherwise if \( m \% n = 0 \), then \( n | m \) and \( \gcd{\left ( m , n \right )} = n \)

If \( m \% n = 0 \), then \( m = \left ( m / / n \right ) \cdot n \), therefore \( \gcd{\left ( m , n \right )} = \gcd{\left ( \left ( m / / n \right ) \cdot n , n \right )} = n \), so now assume that \( m \% n > 0 \)

Recall that \( m = \left ( m / / n \right ) \cdot n + m \% n \), therefore \( m - \left ( m / / n \right ) \cdot n = m \% n \), so that if \( d \) divides both \( m , n \), then it must divide \( m \% n \) (and clearly \( n \)), and by the original equation if \( d \) is a divisor of both \( n , m \% n \) then \( d \) divides \( m \) (and clearly \( n \)).

The above paragraph shows that a number is a divisor of \( m , n \) if and only if it is a divisor of \( n , m \% n \), which shows that their set of divisors are equal and thus \( \gcd{\left ( m , n \right )} = \gcd{\left ( n , m \% n \right )} \)

bounded sum implies one less then half

Suppose that \( x , y , b \in \mathbb{N}_{1} \) and \( x < y \) with \( x + y \le b \), then \( x < \frac{b}{2} \)

Suppose for the sake of contradiction that \( x \ge \frac{b}{2} \), then we know that \( y > x \ge \frac{b}{2} \) so therefore \( x + y \gt \frac{b}{2} + \frac{b}{2} = b \), so we have \( x + y > b \) which is a contradiction so that \( x < \frac{b}{2} \).

euclidean algorithm has exponentially decreasing remainders

Let \( a , b \in \mathbb{N}_{1} \) with \( a \ge b \) be two integers, and suppose we will preform the euclidean algorithm on them to compute \( \gcd{\left ( m , n \right )} \), supposing that \( r_{k} \) represents the remainder after \( k \) (where \( k \in \mathbb{N}_{1} \)) steps into the euclidean algorithm, then \( r_{2 n} \lt \frac{b}{2^{n}} \)

For the base case, suppose that \( n = 1 \), so we'd like to prove that \( r_{2} \lt \frac{b}{2} \). Firstly we know that \( a = b q_{0} + r_{0} \) with \( 0 \le r_{0} \lt b \), then applying the next iteration we have \( b = r_{0} q_{1} + r_{1} \) with \( 0 \le r_{1} \lt r_{0} \) and one more time, we get \( r_{0} = r_{1} q_{2} + r_{2} \) with \( 0 \le r_{2} \lt r_{1} \), this shows us that \( b = \left ( r_{1} q_{2} + r_{2} \right ) q_{1} + r_{1} \).

Since \( a \ge b \), \( b \gt r_{0} \) and \( r_{0} \gt r_{1} \), then \( q_{0} \ge 1 \), \( q_{1} \ge 1 \) and \( q_{2} \ge 1 \), therefore \( b = \left ( r_{1} q_{2} + r_{2} \right ) q_{1} + r_{1} \ge \left ( r_{1} \cdot 1 + r_{2} \right ) \cdot 1 + r_{1} \ge r 1 + r 2 \) therefore \( r_{2} < \frac{b}{2} \) which concludes the base case

Now let \( k \in \mathbb{N}_{1} \) assuming that \( r_{2 k} \le \frac{b}{2^{k}} \), we want to prove that \( r_{2 \left ( k + 1 \right )} = \frac{b}{2^{k + 1}} \), noting that \( 2 \left ( k + 1 \right ) = 2 k + 2 \).

To start let's say we have an intance of the euclidean algorithm that lasts for at least \( 2 k + 2 \) iterations, therefore we know that \( r_{2 k} \le \frac{b}{2^{k}} \) by our induction hypothesis, additionally at the \( 2 k \)-th iteration we would have an equation of the form \( r_{2 k} = r_{2 k + 1} \left ( q_{2 k + 2} \right ) + r_{2 k + 2} \), since we know that \( r_{2 k + 1} > r_{2 k + 2} \), then \( q_{2 k + 2} \ge 1 \), which then shows that \( r_{2 k} = r_{2 k + 1} \left ( q_{2 k + 2} \right ) + r_{2 k + 2} \ge r_{2 k + 1} + r_{2 k + 1} \), and since \( \frac{b}{2^{k}} \gt r_{2 k} \) , then we know that \( r_{2 k + 2} \lt \frac{1}{2} \cdot \frac{b}{2^{k}} = \frac{b}{2^{k + 1}} \) which is what we needed to show

upper bound on euclidean algorithm iterations

The euclidean algorithm terminates in at most \( 2 \log_{2}{\left ( b \right )} \) iterations

The euclidean algorithm terminates in \( k \) iterations if and only if \( r_{k} = 0 \), we know that for all \( n \in \mathbb{N}_{1} \) that \( r_{2 n} \lt \frac{b}{2^{n}} \), therefore when \( n = \log_{2}{\left ( b \right )} \), then we have \( r_{2 \log_{2}{\left ( b \right )}} \lt \frac{b}{2^{\log_{2}{\left ( b \right )}}} = \frac{b}{b} = 1 \), but if \( r_{2 \log_{2}{\left ( b \right )}} \lt 1 \), then since the remainders are always elements of \( \mathbb{N}_{0} \), then we know that \( r_{2 \log_{2}{\left ( b \right )}} = 0 \), thus we've shown after \( 2 \log_{2}{\left ( b \right )} \) iterations the algorithm must terminate

multiplicative function

an arithmetic function is said to be multiplicative when

\( f{\left ( m \right )} \cdot f{\left ( n \right )} = f{\left ( m \cdot n \right )} \)

for all coprime positive integers \( m , n \)

Suppose that \( d \left ( n \right ) \) is the number of divisors of \( n \), then \( d \) is a multiplicative function.

Let \( m , n \in \mathbb{Z}^{+} \) and assume that \( \gcd{\left ( m , n \right )} = 1 \), we'd like to prove that \( d \left ( m \right ) \cdot d \left ( n \right ) = d \left ( m \cdot n \right ) \)

Suppose that the divisors of \( m \) are \( P = \left \lbrace p_{1} , \ldots , p_{j} \right \rbrace \) and the divisors of \( n \) are \( Q = \left \lbrace q_{1} , \ldots , q_{k} \right \rbrace \)

Claim that the set \( P \cdot Q = \left \lbrace p_{x} \cdot q_{y} : x \in \left [ j \right ] , y \in \left [ k \right ] \right \rbrace \) is exactly equal to the divisors of \( m \cdot n \)