TMA4155 – exercise 3

Exercise 24, page 108 in Trappe & Washington

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} \]

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}\).)

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

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\).