A deeper dive into modular arithmetic

July 26, 2023

This will be updated after our meeting! First, here are a few definitions and links that we didn’t talk about yesterday.

Any prime number of the form \(2^p -1\) for \(p\) prime is called a Mersenne prime. Any integer of the form \(2^k+1\) is called a Fermat prime.

A natural question is to ask if there are infinitely many Mersenne or Fermat primes.

  • There are only five known Fermat primes: 3, 5, 17, 257, and 65537. More generally, mathematicians study Fermat numbers. You can find more information about this on the oeis. (online encyclopedia of integer sequences)
  • There are about fifty known examples of Mersenne primes. The “Great Internet Mersenne Prime Search” (GIMPS) is a collaborative effort devoted to finding new Mersenne primes. If you’re (or your computer) lucky enough to find one, there is a cash reward.

There are also a few (big!) unsolved problems, or conjectures that ought to be mentioned:

Conjecture. (Twin prime conjecture) Are there infinitely many primes \(p\) such that \(p+2\) is also prime?

Conjecture.(Goldbach conjecture) Can every even integer be written as a sum of two primes?

Conjecture.(Legendre) Is there always a prime between two perfect squares?

At this point, we’ve sufficiently convinced ourselves that there are a lot of unproven statements about primes. There’s also many things we can say:

Theorem. There are infinitely many primes of the form \(4k+3\).

Infact, the above theorem is true more generally.

Theorem. (Dirichlet's Theorem on Primes in an Arithmetic Progression) There are infinitely many primes of the form \(ak+b\) for \((a,b)=1\).

Theorem. (Green, Tao) There exist arbitrarilty long arithmetic progressions of primes.

We also noted in class that the above theorem is true for composite numbers as well. (There are arbitrarily long arithmetic progressions of composite numbers)

As a group, we helped Momo the cat figure out how many things she has. (Momo borrowed this problem from the Chinese mathematician Sun Zi. Momo can’t actually count.)

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?

Sun Zi

We saw that the smallest number of things that Momo could possibly have is \(23\). The more accurate solution is

\(things \equiv 23 \mod 105\).

Finally, we saw a precise statement of our problem:

Theorem.Modular Remainder Theorem Suppose \(n_1, n_2, \dots, n_k\) are positive integers that are pair-wise relatively prime. Then, the system of equations \(x\equiv a_1\mod n_2\), \(\dots\), \(x\equiv a_k \mod n_k\) has a unique solution modulo \(n_1\cdots n_k\).

hide challenge problems
If you've seen this material before or want something to think about, here are some problems for you! Unless otherwise stated, all variables are assumed to be integers.

  1. The Fundamental Theorem of Arithmetic was mentioned yesterday-- so let's try to use it. Do there exist \(n,m\in\mathbb{Z}\) such that \(7m^2=n^2\)? Why or why not?
  2. Show that for all \(n\in\mathbb{N}\), \((n, n+1) = 1\).
  3. Find the natural number \(k\) so that \(2^{50}\equiv k \mod 7\). Hint: \(k\leq 6\).
  4. In our meeting today, we will talk about primes in arithmetic progression. Can you convince yourself that there are infinitely many prime numbers of the form \(4n+3\)? More generally, if \((a,b)=1\), are there infinitely many primes of the form \(an + b\)?
  5. This isn't necessarily a number theory problem, but I think some of you will find it interesting. Given an integer \(n\), define a function \(f(n)\) as follows: \( f(n) = \begin{cases} n/2 &\text{if } n\equiv 0 \mod 2\\ 3n+1 &\text{if } n\equiv 1\mod 2 \end{cases}\)
    Once you compute \(f(n)\), make the result your new \(n\). Repeat this process until you can't anymore. You'll notice that once \(n=1\), you'll run into a loop. Do you think this process always ends in 1, regardless of which \(n\) was chosen to start? This is called the Collatz Conjecture.
<- back