189-245A: Algebra 1

Assignment 2

Due: Monday, September 29.

1. Let $R$ be the set of elements of the form $a+b\sqrt{-5}$, where $a$ and $b$ are in ${\bf Z}$. Show that $R$ is a ring by using the fact that you already know this for the complex numbers. An element $p$ of $R$ is said to be a prime in $R$ if any divisor of $p$ in $R$ is either $1$, $-1$, $p$, or $-p$. Show that $p=3$ is a prime in $R$. Find elements $x$ and $y$ in $R$ such that $p=3$ divides $xy$ but $p$ divides neither $x$ nor $y$. (This shows that the analogue of Gauss's lemma fails to be true in $R$.)

2. Solve the following congruence equations:

(a) $4x \equiv 3 \pmod{7}$;

(b) $5x\equiv 2 \pmod{11}$;

(c) $3x\equiv 6 \pmod{15}$;

(d) $6x\equiv 14 \pmod{21}$.

3. Show that $a^5\equiv a \pmod{30}$, for all integers $a$.

4. Find an element $a$ of $\mathbb Z/{13}\mathbb Z$ such that every non-zero element of this ring is a power of $a$. (An element with this property is called a primitive root mod $13$.) Can you do the same in $\mathbb Z/{24}\mathbb Z$?

5. Prove or disprove: if $a^2 =b^2$ in $\mathbb Z/n\mathbb Z$, and $n$ is prime, then $a=b$ or $a=-b$. Give an example, when $n$ is not prime, of two elements of $\mathbb Z/n\mathbb Z$ whose squares are equal, yet are not equal up to sign.

6. List the invertible elements of $\mathbb Z/{24}\mathbb Z$ and $\mathbb Z/{9}\mathbb Z$.

7. The following exercise requires you to use Pari-GP, which you can download for free from the internet.

1. For $n\ge 0$, the integer $N=2^{2^n}+1$ is called the $n$-th Fermat number. Show that $2^N\equiv 2 \pmod{N}$ for all $n\ge 0$. (Without the computer).

2. The first 5 Fermat numbers, $3$, $5$, $17$, $257$, and $65537$, are known to be prime. Convince yourself of this by computing $3^N$ modulo $N$ for these numbers. (Using Pari).

3. Show that the next few Fermat numbers $N=2^{2^n}+1$ with $5\le n \le 12$ are all composite, by calculating $3^N$ modulo $N$ for these values of $n$..

Remark. As you will see, these numbers get quite large, and some delicacy is required with the calculation. In Pari, typing a command line
N=2^(2^(12))+1; Mod(3^N,N)
is apt to cause an overflow, while
N=2^(2^(12))+1; Mod(3,N)^N
is pretty fast. Can you explain why?

Although the 12th Fermat number is known to be composite (and indeed you will have shown it with your calculation), no prime divisor of this 1233 digit integer is currently known.

8. Show that if $n=1729$, then $a^n\equiv a$ (mod $n$) for all $a$, even though $n$ is not prime. Hence the converse to Fermat's Little Theorem is not true. (An integer which is not prime but still satisfies $a^n\equiv a$ (mod $n$) for all $a$ is sometimes called a strong pseudo-prime, or a Carmichael number. It is known that there are infinitely many Carmichael numbers (cf.~Alford, Granville, and Pomerance. There are infinitely many Carmichael numbers. Ann. of Math. (2) 139 (1994), no. 3, 703--722.) The integer $1729$ was the number of Hardy's taxicab, and Ramanujan noted that it is remarkable for other reasons as well. For instance, it is the smallest positive integer that can be expressed as a sum of two cubes in two different ways. (See G.H. Hardy, A mathematician's apology.)

9. Show that if $p$ is prime, and $\gcd(a,p)=1$, then $a^{(p-1)/2}\equiv 1$ or $-1$ (mod $p$). More generally, show that if $p-1= 2^r m$ with $m$ odd, the sequence $$ (a^{(p-1)}, a^{(p-1)/2}, a^{(p-1)/4}, \ldots, a^{(p-1)/2^r}) $$ (taken modulo $p$) starts of with sequence of $1$'s, and that the first term that differs from $1$ is equal to $-1 \pmod{p}$. Show that this statement ceases to be true when $p=1729$. This remark is the basis for the Miller-Rabin primality test which is widely used in practice.

10. Check that the number $252097800623$ is prime using the Miller-Rabin test and PARI, with $a$ running between $2$ and $10$.