# TMA4155 – exercise 3

## 2010-10-04

### 1 – Chinese remainder theorem

Exercise 24, page 108 in Trappe & Washington

### 2 – Chinese remainder theorem

Solve the system of congruence relations: $\begin{split} x&\equiv1\pmod 2\\ x&\equiv2\pmod 3\\ x&\equiv3\pmod 5\\ x&\equiv4\pmod 7\\ \end{split}$

### 3 – Modular exponentiation

Let $z=2^{8500}\bmod 10403$.

1. Notice that $10403=101\cdot103$. Show that if you know $x=2^{8500}\pmod{101}$ and $y=2^{8500}\pmod{103}$, you can compute $2^{8500}\pmod{10403}$ using the Chinese Remainder Theorem.
2. Use Fermat’s Little Theorem and exponent arithmetic to compute $x$ and $y$.
3. Compute $z$.

(Misprint corrected 2010-10-31. Was: $z=28500\pmod{10403}$.)

### 4 – Factorization

5688209 is the product of two primes that are very close to each other. Find these primes.

### 5 – Factorization

With $n=2487607$ it is a fact that $\begin{split} 2733^2&\equiv2^2\cdot3\cdot 7^2\cdot11\pmod{n},\\ 16007^2&\equiv2^4\cdot3\cdot11\pmod{n}. \end{split}$ Use these congruences to find a nontrivial factor of $n$.