189-235A: Algebra 1

Assignment 4

Week of Sept 28-October 2

1. Let $R$ be the ring of elements of the form $a+b\sqrt{-5}$, where $a$ and $b$ are in ${\bf Z}$. 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/{120}\mathbb Z$ and $\mathbb Z/{9}\mathbb Z$.

7. Prove that the integer $437$ is composite without attempting to factor it, by computing $2^{437}$ in $\mathbb Z/437 \mathbb Z$. It is OK (in fact, it is advised) to use a calculator, but clearly indicate the steps in your calculation. (You need not be fastidious in justifying your arithmetic in $\mathbb Z/437\mathbb Z$, though. So it is perfectly OK to write $512 = 75$ or $436=-1$ without further ado.)

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. (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. Try to factor the integer $$ n= 685446526579731898863912268042143879229926400466437251534352674891237471274951148527386914734600982134977247323286400719094979241552359086027789170981826463314793733997736602235016142430761062403224974459491$$ using Pari-GP or other computer algebra system. Suppose you are told that one of the prime factors is a Mersenne prime, of the form $2^m-1$. How might this help you factor $n$? (Hint: compute the residue of $2^{600!}-1$ modulo $n$, and take its gcd with $n$. What do you observe? Why did this work?)