Numbers and divisibility

July 24, 2023

Our two main goals for the course are the following:

  • Develop a common language to describe patterns that we see.
  • Find our own patterns, and determine their validity.

First, we discussed what kind of numbers we’ll be studying this week. We defined the natural numbers \(\mathbb{N}\) to be \(\{1, 2, 3, \dots\}\). Similarly, the integers \(\mathbb{Z}\) are \(\{\dots, -1, 0, 1, 2, \dots\}\).

So, how might one consider studying elements of \(\mathbb{N}\) and \(\mathbb{Z}\)? As some of you mentioned during our meeting, one approach is to figure out how two numbers (or sets of numbers) are related to eachother. For example, we can determine how similar two numbers are by looking at their divisors.

Suppose \(a, b\in \mathbb{Z}\). We will say that \(b\) divides \(a\), written as \(b\mid a\), if and only if there exists another integer \(c\) so that \(a=bc\). When this occurs, \(b\) is called a divisor of \(a\).

Example. Let \(n\in \mathbb{Z}\), and suppose that \(6\mid n\). Can you show that \(3\mid n\) using the definition above?

A common divisor of \(a,b\in \mathbb{Z}\) is another integer \(c\) so that \(c\mid a\) and \(c\mid b\).
The greatest common divisor of \(a, b \in \mathbb{Z}\), written as \(gcd(a,b)\) (or just \((a,b)\)), is the biggest \(c\in\mathbb{Z}\) so that \(c\) divides both \(a\) and \(b\).
We say that \(a,b\) are relatively prime or coprime if \(gcd(a,b)=1\).
A natural number \(p>1\) is prime if and only if \(p\) is not the product of natural numbers less than \(p\).
On the other hand, a natural number \(n\) is composite if and only if \(n\) is a product of natural numbers less than \(n\).

Example. Come up with two composite integers \(a, b\) that are relatively prime.

Exercise. If \(a,b\) are nonzero integers, can you find \(u,v\in\mathbb{Z}\) so that \(gcd(a,b)= au + bv\)? Is this always true? (This is called Bezout’s identity!)

A natural number \(p>1\) is prime if and only if \(p\) is not the product of natural numbers less than \(p\). On the other hand, a natural number \(n\) is composite if and only if \(n\) is a product of natural numbers less than \(n\).

During our meeting, we noticed that if \(n\) is odd, it can be written as \(n = 2k+1\) for some \(k\in \mathbb{Z}\). On the other hand, if \(n\) is even, it can be written as \(n = 2s\). We generalized this in the following definition.

Let \(a,b,n \in \mathbb{Z}\). We say that \(a,b\) are congruent modulo \(n\) if and only if \(n\) divides \((a-b)\). Notationally, we write this as \(a\equiv b \mod n\).

In our meeting, we encountered the following question:

Question. What if \(n = 0\) in the above congruence?

You’re encouraged to think about what this could mean! (How would it impact our definition? What does it mean to divide by zero?)

Example. On Zoom, we wanted to find \(a\) so that \(a\equiv 2 \mod 3\). Remember, this means that when \(a\) is divided by 3, it leaves a remainder of 2. We saw that \(a\) could be, for example, 5. More generally, \(a\) must have the form \(a=3k+2\) for \(k\in\mathbb{Z}\).

Example. Suppose we know that \(k\equiv 2\mod 7\). Is it also the case that \(k\equiv 3\mod 2\)?

<- back