Midterm 1: Building Your Number Theory Toolkit 🔢

Welcome, students! In this lesson, you will learn the main ideas behind Midterm 1 in Number Theory and how those ideas connect to arithmetic functions, divisors, and future topics in the course. Midterm material in number theory usually focuses on the basic language of integers, divisibility, prime numbers, congruences, and proof techniques. These ideas are the foundation for studying arithmetic functions later, such as divisor sums and multiplicative functions. 🎯

What you should learn in this lesson

By the end of this lesson, you should be able to:

explain the main terminology used in the Midterm 1 material,
use number theory methods to solve problems about divisibility and primes,
recognize how early number theory ideas support arithmetic functions,
summarize why Midterm 1 matters in the larger course, and
use examples and evidence to justify your answers.

The language of number theory

Number theory begins with the integers $\mathbb{Z}$. These are the whole numbers and their negatives, such as $-3$, $0$, $7$, and $18$. A central idea is divisibility. We say that $a$ divides $b$, written $a \mid b$, if there exists an integer $k$ such that $b = ak$.

For example, $3 \mid 15$ because $15 = 3 \cdot 5$, but $4 \nmid 15$ because there is no integer $k$ with $15 = 4k$. This idea is simple, but it powers many later results. Divisibility tells us how integers break into factors, how primes work, and how sums over divisors are built.

A closely related idea is the greatest common divisor. The greatest common divisor of two integers $a$ and $b$, written $\gcd(a,b)$, is the largest positive integer that divides both. For example, $\gcd(18,30)=6$. This means $6$ is the largest integer dividing both $18$ and $30$.

The least common multiple, written $\operatorname{lcm}(a,b)$, is the smallest positive integer that is divisible by both $a$ and $b$. For example, $\operatorname{lcm}(4,6)=12$. These two ideas are connected by the formula

$\gcd(a,b)\operatorname{lcm}(a,b)=|ab|.$

This formula is often useful when solving problems quickly and checking answers. ✅

Prime numbers and factorization

A prime number is an integer greater than $1$ whose only positive divisors are $1$ and itself. Examples include $2$, $3$, $5$, $7$, and $11$. A number greater than $1$ that is not prime is called composite. For example, $12$ is composite because $12 = 3 \cdot 4 = 2^2 \cdot 3$.

The most important theorem here is the Fundamental Theorem of Arithmetic. It says that every integer greater than $1$ can be written as a product of primes, and this factorization is unique up to the order of the primes. For example,

84 = 2^$2 \cdot 3$ $\cdot 7$.

This factorization is unique in the sense that no other prime-product uses different primes or exponents to make $84$. This theorem is one reason number theory is so powerful: it lets us study integers through their prime building blocks.

A useful way to think about this is through real life. Suppose you are organizing a class event and need $84$ snacks split evenly into bags. Prime factorization helps you see possible ways to group them. Because $84 = 2^2 \cdot 3 \cdot 7$, you can make equal groups of $2$, $3$, $4$, $6$, $7$, $12$, $14$, $21$, $28$, or $42$ snacks. The divisors are not random; they come from the prime factorization.

Congruences and modular arithmetic

One of the major ideas in Midterm 1 is congruence. We say

$a \equiv b \pmod{n}$

if $n \mid (a-b)$. This means $a$ and $b$ leave the same remainder when divided by $n$.

For example,

$17 \equiv 2 \pmod{5}$

because $17-2=15$, and $5 \mid 15$. Congruence is the language of modular arithmetic, which is used everywhere from calendars to computer science to encryption. 🔐

Why is this important? Because many problems become easier when we only care about remainders. For instance, if you want the last digit of a power like $7^{10}$, working modulo $10$ can simplify the computation. Instead of dealing with a huge number, you study its remainder pattern.

Congruence respects arithmetic operations. If

a $\equiv$ b \pmod{n} \quad \text{and} \quad c $\equiv$ d \pmod{n},

then

$a+c \equiv b+d \pmod{n}$

and

$ac \equiv bd \pmod{n}.$

These rules let you replace numbers by simpler equivalent numbers without changing the answer modulo $n$.

The Euclidean Algorithm and Bézout’s identity

A fast way to compute $\gcd(a,b)$ is the Euclidean Algorithm. It uses repeated division with remainder. For example, to find $\gcd(252,198)$, divide:

252 = $198 \cdot 1$ + 54

198 = $54 \cdot 3$ + 36

54 = $36 \cdot 1$ + 18

36 = $18 \cdot 2$ + 0.

The last nonzero remainder is $18$, so $\gcd(252,198)=18$.

This algorithm matters because it is efficient and because it leads to Bézout’s identity. This identity says that for integers $a$ and $b$, there exist integers $x$ and $y$ such that

$ax+by=\gcd(a,b).$

For $252$ and $198$, we can write $18$ as a combination of those numbers by working backward through the division steps. This kind of representation is useful in solving linear Diophantine equations and in understanding inverses modulo $n$.

A key fact is that an integer $a$ has a multiplicative inverse modulo $n$ exactly when

$\gcd(a,n)=1.$

That means $a$ and $n$ are relatively prime. For example, $3$ has an inverse modulo $7$ because $\gcd(3,7)=1$. In fact, $3 \cdot 5 = 15 \equiv 1 \pmod{7}$, so $5$ is the inverse of $3$ modulo $7$.

Why Midterm 1 connects to arithmetic functions

Midterm 1 is not separate from arithmetic functions; it prepares you for them. An arithmetic function is a function whose input is usually a positive integer and whose output is a number. Common examples include the divisor-counting function $\tau(n)$, the sum-of-divisors function $\sigma(n)$, and the Euler totient function $\varphi(n)$.

These functions depend on divisibility, prime factorization, and congruence. For example, to find $\sigma(12)$, you first list the divisors of $12$:

1, 2, 3, 4, 6, 12.

Then add them:

$\sigma(12)=1+2+3+4+6+12=28.$

This is a simple example of a divisor sum. If you know the prime factorization $12 = 2^2 \cdot 3$, you can study divisors more systematically. That is why prime factorization is such an important bridge between Midterm 1 and later topics.

A function like $\varphi(n)$ also uses the midterm tools. The value $\varphi(n)$ counts how many integers from $1$ to $n$ are relatively prime to $n$. For example, $\varphi(8)=4$ because the numbers $1$, $3$, $5$, and $7$ are relatively prime to $8$. To understand this count, you need gcd ideas, divisibility, and factorization.

Solving problems with evidence and reasoning

In number theory, it is not enough to guess an answer. You should explain why it is true using definitions, theorems, or examples. For instance, suppose you want to show that $6 \mid (3n)$ whenever $n$ is even. If $n$ is even, then $n=2k$ for some integer $k$. So

$3n = 3(2k)=6k,$

which means $6 \mid (3n)$. This is a proof using the definition of even numbers and divisibility.

Another common strategy is checking a pattern with examples and then justifying it. For example, consider numbers modulo $4$. The square of any integer is congruent to either $0$ or $1$ modulo $4$:

0^$2 \equiv 0$ \pmod{4},\quad 1^2 $\equiv 1$ \pmod{4},\quad 2^2 $\equiv 0$ \pmod{4},\quad 3^2 $\equiv 1$ \pmod{4}.

This kind of evidence helps you make a conjecture, and then the theorem proves it. This is an important habit in number theory: examples guide discovery, but proof confirms truth.

Conclusion

Midterm 1 in Number Theory gives you the core tools for the rest of the course. You learned the meaning of divisibility, gcd, lcm, prime factorization, congruence, and the Euclidean Algorithm. You also saw why these ideas matter for arithmetic functions such as $\tau(n)$, $\sigma(n)$, and $\varphi(n)$. Together, these ideas form a toolkit for reasoning about integers. If you understand this material well, students, you will be ready to study divisor sums, multiplicative functions, and deeper results in number theory. 🌟

Study Notes

The integers are written as $\mathbb{Z}$.
$a \mid b$ means $a$ divides $b$, so $b=ak$ for some integer $k$.
$\gcd(a,b)$ is the greatest common divisor, and $\operatorname{lcm}(a,b)$ is the least common multiple.
The relationship $\gcd(a,b)\operatorname{lcm}(a,b)=|ab|$ is useful for computations.
A prime has exactly two positive divisors: $1$ and itself.
Every integer greater than $1$ has a unique prime factorization.
$a \equiv b \pmod{n}$ means $n \mid (a-b)$.
Congruence lets you work with remainders instead of full numbers.
The Euclidean Algorithm finds $\gcd(a,b)$ efficiently.
Bézout’s identity says $ax+by=\gcd(a,b)$ for some integers $x$ and $y$.
An integer $a$ has an inverse modulo $n$ exactly when $\gcd(a,n)=1$.
Arithmetic functions like $\tau(n)$, $\sigma(n)$, and $\varphi(n)$ depend on divisors and prime factors.
Divisor sums, such as $\sigma(12)=28$, show how Midterm 1 connects to later topics.