Update Aug 8, 21:25: Please notice that a new pdf, titled prim3, has been added below.

Dear all,

Here are the chapters that you will be examined on for the final:

1.1, 1.3, 1.5

3.1, 3.2, 3.3, 3.4, 3.5, 3.7

4.1, 4.2, 4.3

5.1

6.1, 6.2, 6.3

7.1, 7.2, 7.3

9.1, 9.2, 9.3

I will cover 7.3 in the class tomorrow.

I will post some notes on primitive roots on the blog page.

Two PDFs:
prim, prim2, prim3

## July 23–24

Euler’s theorem and its one-line proof has already been mentioned in the blog entry “July 15–17”, so we don’t repeat it here.

We introduced the concepts of arithmetic functions, multiplicative functions and completely multiplicative functions. By the fundamental theorem of arithmetic, a multiplicative function is determined by its values on primes powers, and a completely multiplicative function is determined by its values on primes. For example, define a function $\mu$ on primes powers by $\mu(p)=-1$ and $\mu(p^e)=0$ if $e>1$; then one can extend $\mu$ to a multiplicative function, which we again denote by $\mu$. This is called the Möbius function. It is an important function in analytic number theory.

The Euler’s totient function $\varphi(n)$ counts the number of positive integers $b\le n$ such that $(b,n)=1$. This is a multiplicative function, but it’s not completely multiplicative. The explicit formula: Write $n=p_1^{e_1}\cdots p_t^{e_t}$; then

$\varphi(n)= n(1-1/p_1)\cdots (1-1/p_t)$.

In the class, Sujatha first proved that $\varphi(n)$ is multiplicative and then deduced this formula. Here is how to prove it directly, using the inclusion–exclusion principle (see the blog entry “Lecture 3–4”). Let $S_i=\{1\le b\le n: p_i\mid b\}$. Then
$S_i\cap S_j=\{1\le b\le n: p_ip_j\mid b\}$, $S_i\cap S_j\cap S_k=\{1\le b\le n: p_ip_jp_k\mid b\}$, etc.
Clearly we have
$|S_i|=n/p_i, \quad |S_i\cap S_j|=n/p_ip_j,\quad |S_i\cap S_j\cap S_k|=n/p_ip_jp_k$, etc.
By the inclusion–exclusion principal, we have

\begin{aligned} \varphi(n)& = n-|S_1\cup \cdots \cup S_t| \\ & = n-\sum |S_i|+\sum |S_i\cap S_j|-\cdots +(-1)^t |S_1\cap\cdots \cap S_t| \\ & =n-\sum n/p_i+\sum n/p_ip_j-\cdots +(-1)^t n/p_1\cdots p_t \\ & =n\Big(1-\sum 1/p_i+\sum 1/p_ip_j-\cdots +(-1)^t 1/p_1\cdots p_t\Big) \\ & =n(1-1/p_1)\cdots (1-1/p_t)\end{aligned}.

## July 18, 22

The converse of Fermat’s little theorem is not true. That is to say, given an integer $b$, there are composite numbers $n$ such that $b^{n-1}\equiv 1\pmod n$. Such an integer is called a pseudoprime to the base b. If $n$ is a base b pseudoprime for every $b$ which is relatively prime to $n$, then $n$ is called a Carmichael number. There are infinitely many Carmichael numbers. Unlike the prime number theorem, the explicit asymptotic distribution of Carmichael numbers is not known.

** In 1899, Korselt obtained the following criterion: A positive composite integer $n$ is a Carmichael number if and only if $n$ is square-free and $p-1\mid n-1$ for every prime factor $p$ of $n$. For those who know group theory, a Carmichael number $n$ is a composite integer such that the order of every element $b\in (\mathbf{Z}/n)^\times$ divides $n-1$. On the other hand, the structure of $(\mathbf{Z}/n)^\times$ is explicitly known, thus Korselt’s criterion becomes a simple exercise.

Suppose that n, b are integer with n odd. We say that n passes the Miller–Rabin’s test for the base b if either $b^{(n-1)/2}\equiv \pm 1 \pmod n$. A composite number that passes the Miller–Rabin’s test for the base b is called a strong pseudoprime to the base b. Of course such a number is necessarily a pseudoprime.

** Given a fixed base b, there are infinitely many strong pseudoprimes to the base b. However, there is no analogue of the Carmichael numbers in the “strong” case. To be precise, if $n$ is an odd composite integer, then n passes Miller–Rabin’s test for at most $(n-1)/4$ bases b with $1\le b\le n-1$.

Under the assumption of the generalized Riemann hypothesis, for every positive integer n, there is an integer $1\le b\le 2(\log n)^2$, such that n fails Miller–Rabin’s test for the base b. The best, unconditional and deterministic primality test currently known is due to Agrawal, Kayal and Saxena. For details, see here.

## Assingment 5 (Midterm exam)

1 Show that if $k>1$ is an integer, then the equation $\tau(n)=k$ has infinitely many solutions.

2 Which positive integers have an odd number of divisors?

3. Decrypt the message RTOLK TOIK which was encrypted using affine transformation $C\equiv 3P+24$ mod $26$.

4. This is a problem on exponentiation cipher. Let $p=2633$ and $e=29$, so that $(29, 2633)=1$.
(a) Check that the block length $m=4$ in this case.
(b) Write down the encryption formula for the cipher text and decryption formula, given that 2269 is an inverse of 29 mod 2632.
(c) Write the plaintext block in numbers for THIS IS AN EXAM.

5. Determine $\mathrm{ord}_{10}3$, $\mathrm{ord}_{1} 310$, $\mathrm{ord}_{17}2$.

## Homework 3

1. Use fast modular exponentiation to compute the remainder of $2^{200}$ modulo 47.
Answer:: 21. For details, use this online calculator.

2. Find an integer that leaves a remainder of 9 when it is divided by either 10 or 11, but is divisible by 13.
Answer: This is a Chinese remainder theorem problem. Rephrasing, it asks for a solution of the following system of congruence equations: $x\equiv 9\pmod {10}$, $x\equiv 9\pmod{11}$, $x\equiv 0 \pmod {13}$. All solutions are $559+1430n$. Any number in this sequence is a correct solution. For details, use this online calculator.

3. A troop of 17 monkeys store their bananas in 11 piles of equal size, each containing more than 1 banana, with a twelfth pile of 6 left over. When they divide the bananas into 17 equal groups, none remain. What is the smallest number of bananas they can have?

Another Chinese remainder theorem problem. Answer: 204.

4. Determine if $\mathrm{(3EA235)}_{16}$ and $\mathrm{(F117921173)}_{16}$ are divisible by 5.
Answer: $3+E+A+2+3+5=32$, which is not divisible by 5. Therefore $\mathrm{(3EA235)}_{16}$ is not divisible by 5. Similarly, $\mathrm{(F117921173)}_{16}$ is not divisible by 5 either.

5. A base b palindromic integer is an integer whose base b representation reads the same forward and backward. (For example, 12321 is a palindromic integer in base 10.) Show that every decimal palindromic integer with an even remainder of digits is divisible by 11. (Hint: $10^s+10^{(2n-1)-s}\equiv 0 \pmod{11}$.)
Proof: Suppose that the integer has $2n$ digits. Since it is palindromic, the coefficients (digits) before $10^{s}$ and $10^{2n-1-s}$ are the same, say $a_s$. Then we have

$a_s(10^s+10^{2n-1-s})=a_s((-1)^s+(-1)^{2n-1-s})=a_s\cdot 0=0 \pmod {11}$,

because one of $s$, $2n-1-s$ is odd and the other is even. But the integer we consider is the sum of the numbers of the form $a_s(10^s+10^{2n-1-s})$, and each is divisible by 11. So we are done.

6. Using Fermat’s little theorem, find the least positive residue of $3^{999,999,999}$ mod 7.
Solution: Fermat’s little theorem tells us that $3^6\equiv 1\pmod 7$. Notice that $999,999,999=6\times 166,666,666+3$; thus

$3^{999,999,999}=(3^6)^{166,6666,666}\times 3^3\equiv 1 \times 27 \equiv 6 \pmod 7.$

7. Show that $1^p+2^p+\cdots+(p-1)^p\equiv 0 \pmod p$, when $p$ is an odd prime.
Proof: Fermat’s little theorem tells us that $b^p\equiv b \pmod p$ whenever $(b,p)=1$.
Hence

$1^p+2^p+\cdots (p-1)^p\equiv 1+2+\cdots +(p-1) =p\cdot \frac{p-1}2\equiv 0\pmod p$.

(Notice that $(p-1)/2$ is an integer because $p$ is odd.)

8. Show that 45 is a pseudoprime to the base 17 and 19.
Proof: We have $17^4= 83521 =1856\times 45+1\equiv 1\pmod {45}$. Therefore $17^{44}=(17^4)^{11}\equiv 1\pmod {45}$. So 45 is a base 17 pseudoprime. The case for 19 is even simpler: notice that $19^2=381\equiv 1\pmod{45}$.

## July 15–17

Since I no longer attend the class, the following notes are based on the information provided by Sujatha and the corresponding sections in the textbook.

The base b representation of an integer is covered in the 2nd chapter of the book, which is not included in the course line. The idea is simple. Any integer $n$ in decimal expansion is written as
$n=a_s\times 10^s+a_{s-1}\times 10^{s-1}+\cdots+a_0\qquad 0\le a_i<10$.
The base $b$ representation is just replacing 10 by $b$, and write
$n=a_t'\times b^t+a_{t-1}'\times b^{t-1}+\cdots+a_0'\qquad 0\le a_i'.
How to determine the digits $a_i'$? You first find integer $t$ such that $b^t \le n< b^{t+1}$ and put $a_t=[n/b^t]$. Then take the difference $n-a_t\cdot b^t$ and repeat the process. This process works for all real numbers (not necessarily integers), except in this case one may get (possibly infinitely many) negative powers of $b$ (the fractional part). Just like the decimal representation, a real number is rational if and only if its base b representation is eventually periodic. If the representation is finite (e.g. an integer), then one should think that there are infinitely many $0$‘s in the fractional part.

The divisibility tests are not important in practice. Computers do division algorithm super fast and, for small numbers, manually doing division algorithm would still be a piece of cake. Theoretically they are merely the simplest applications of congruence. For example, the divisible test for 4 is based on $100\equiv 0\pmod 4$. Therefore in decimal representation, the 3rd digit (from right) $a_2\times 10^2$ and any higher digits $a_s\cdot 10^s$ becomes zero mod 4, and thus can be thrown away.

The check digits is a simple trick to detect errors. Theoretically there is nothing new.

The Wilson’s theorem states that $(p-1)!\equiv -1\pmod p$ if $p$ is a prime. The essence of the proof is the pairing of an integer $a$ with its inverse $a^{-1}$ mod $p$, and the observation that $a\equiv a^{-1} \pmod p$ precisely when $a\equiv \pm 1\pmod p$. Thus, apart from 1 and $p-1$, all other positive integers smaller than $p$ are grouped into pairs and each pair gives 1 mod $p$. On the other hand, if $n$ is composite, then $(n-1)!\equiv 0 \pmod n$ unless $n=4$.

Euler’s theorem states that if $(a,n)=1$, then $a^{\varphi(n)}\equiv 1\pmod n$. (Note. An earlier version of the blog called it Fermat’s little theorem, which is a misnomer.) (Recall that I mentioned Euler’s totient function $\varphi$ in class. You will see more properties of this function later.) For those who know group theory, here is the natural proof: The order of the group $(\mathbf{Z}/n)^\times$ is $\varphi(n)$, thus any element $a\in (\mathbf{Z}/n)^\times$ raised to the power of $\varphi(n)$, would give 1 (the identity).

Fermat’s little theorem is a special case of Euler’s theorem. The statement: If $p$ is a prime which does not divide $a$, then $a^{p-1}\equiv 1\pmod p$.

For “primality tests” coming from Fermat’s little theorem, see the next blog entry.

Judging by the name of the theorem, there should be a “Fermat’s big theorem”. Well, indeed, but it is usually called “Fermat’s last theorem”. The statement: If $n\ge 3$ is an integer, then the equation $x^n+y^n=z^n$ has no solutions in positive integers. It remained open for over 300 years before Andrew Wiles confirmed it in 1994. Speaking of Fermat’s last theorem, we should also mention the famous Catalan’s conjecture, which states that the only integer solution to the equation $x^n-y^m=1$ with $x, y, n,m\ge 2$ is $3^2-2^3=1$. It also remained open for over 150 years before being established by Preda Mihăilescu in 2002.

Another standard conjecture predicts that the gaps between perfect powers tend to infinity. This conjecture is a corollary of the famous abc conjecture. However, both conjectures remain unknown.

There is another interesting, famous, and wide open conjecture: the Collatz conjecture. Start from any positive integer $a_0$. Construct a recursive sequence by

$a_{k+1}=\begin{cases} a_k/2 \quad &\text{if } a_k \text{ is even}, \\ 3a_k+1 \quad &\text{if } a_k \text{ is odd.} \end{cases}$

Then the conjecture predicts that the sequence $a_k$ hits 1.

The reason that I mentioned these conjectures/theorem is to show you that, in number theory, you can ask so many simple questions — questions that can be understood even by elementary schoolchildren, yet their proof, if known, is extremely deep. In case there is an elementary proof (e.g. the prime number theorem), that proof would be super tricky and super complicated. In short, simple questions ≠ easy questions. Of course, there are also tons of questions in number theory that, even to understand the statement would require years of serious study. And so, to provide a proof would be even more difficult.

## Homework 2

Due July 18 (Friday), whether late submission is accepted or not is up to Sujatha.
The exercises all come from the textbook (6th edition). In case you don’t have the book, I copied the questions and posted them here.

These exercises are either simple proofs or direct computations. Don’t be afraid. If you keep good notes in class, you can finish them fairly quickly.

3.1 Exercise (p.76) #12, #18
#12. Show that if $p_k$ is the $k$th prime, then $p_n\le p_1\cdots p_{n-1}+1$.

Proof. Take any prime divisor $p$ of $p_1\cdots p_{n-1}+1$. Then

$p\le p_1\cdots p_{n-1}+1. \hspace{4em} (1)$

Since none of $p_1,\cdots,p_{n-1}$ divides $p_1\cdots p_{n-1}+1$, we see that $p$ is distinct from $p_1,\cdots,p_{n-1}$. In particular,

$p_n\le p. \hspace{9.1em} (2)$

Combining (1) and (2), we are done.

#18. Use Dirichlet’s theorem to show that there are infinitely many primes whose decimal expansion ends with the two digits 23.

Proof. By Dirichlet’s theorem, there are infinitely many primes in the sequence $100n+23$. Clearly, each such prime ends with digits 23 in its decimal expansion.

3.3 Exercise (p.100) #24
#24. Show that if $k$ is a positive integer, then $3k+2$ and $5k+3$ are relatively prime. (Hint: use the “spirit” of the Euclidean algorithm: $(a,b)=(a,b+am)$.)

Proof. Indeed, we have
$(3k+2,5k+3)=(3k+2,2k+1)=(k+1,2k+1)=(k+1,k)=(1,k)=1$.
In each step, I only subtract one copy of the smaller number from the larger one. (Of course, the statement remains true for all integers k.)

3.4 Exercise (p.110) #1 a), b), c), #3
#1. Use the Euclidean algorithm to find each of the following greatest common divisors (gcd).
a) (45, 75)
b) (102, 222)
c) (666, 1414)

Answer. I want to skip the detailed computation. The answers are a) 15; b) 6; c) 2.

#3 For each pair in Exercise #1, express the gcd of the integers as a linear combination of these integers. (That is, you need to write $(a,b)$ as $ax+by$ for some integers $x,y$.) Only do a), b), c) above.

Answer. Detailed computation omitted. (The following are sample answers coming from the Euclidean algorithm. Other answers exist.)
a) $15=2\times 45-1\times 75$.
b) $6= -13\times 102+6\times 222$.
c) $2=-138\times 666+65\times 1414$.

3.5 Exercise (p.123) #44
#44. Show that $\log_2 3$ is irrational. (Hint: Use fundamental theorem of arithmetic (optional) and proof by contradiction.)
Proof. Assume the contrary. Then we can write $\log_2 3=p/q$ where $p,q$ are integers. Then we have $2^{p/q}=3$, or $2^p=3^q$. The LHS is even while the RHS is odd. Contradiction.

3.7 Exercise (p.141) #2 a), b), c)
#2. For each of the following linear Diophantine equations, either find all solutions or show that there are no solutions.
a) $3x+4y=7$
b) $12x+18y=50$
c) $30x+47y=-11$
a) All integer solutions: $x=1+4n$, $y=1-3n$, $n\in \mathbf{Z}$.
b) No integer solutions, because 6 divides the LHS, but not the RHS.
c) All integer solutions: $x=-121+47n$, $y=77-30n$, $n\in \mathbf{Z}$.

4.1 Exercise (p.153) #30, #33
#30. Show by mathematical induction that if $n$ is a positive integer, then $4^n\equiv 1+3n\pmod{9}$.

Proof. The case for $n=1$ is trivial. Now suppose that the congruence holds for $n$. Then

$4^{n+1}=4^{n}\cdot 4\equiv 4(1+3n)=4+12n\equiv 4+3n=1+3(n+1)\pmod 9$,

showing that the formula holds for $n+1$. By induction, the formula holds for all $n$.

#33. Show that if $n\equiv 3\pmod 4$, then $n$ cannot be the sum of the squares of two integers. (Hint: You may find the last problem in Homework 1 useful.)
Proof. If $m$ is an odd integer, then from homework 1, we know $m^2\equiv 1\pmod 4$. If m is even, then plainly $m^2\equiv 0 \pmod 4$. Therefore, the sum of two squares is congruent to 0, 1, or 2 mod 4. But $n\equiv 3 \pmod 4$, thus it cannot be the sum of two integers.

FYI, the set of integers $\{m^2+n^2\}$ is explicitly known. In particular, it contains all primes which are congruence to 1 mod 4.

4.3 Exercise (p.167) #4 c)
#4. Find all the solutions of the following system of linear congruences.
c) $x\equiv 0 \pmod 2 \quad x\equiv 0 \pmod 3 \quad x\equiv 1 \pmod 5 \quad x\equiv 6 \pmod 7$

Answer. Actually you don’t need to compute it using Euclidean algorithm. There is one obvious solution: 6. Therefore by the Chinese remainder theorem, all solutions are: $6+210n$, $n\in \mathbf{Z}$.