Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section12.7Exercises

2

Prove the statement of Lemma 12.1.2 in the case that \(\ell\) is odd.

3

Explain why the extension to Fermat's Little Theorem just before Fact 12.2.1 is true.

4

Check that \(1729\) and \(2821\) are Carmichael numbers.

5

Find a Carmichael number of the form \(7\cdot 23 \cdot p\) for a prime \(p\).

6

Use either the Fermat or Mersenne coprime facts 12.1.4,12.1.8 to provide a different proof that there are infinitely many primes.

7

Pick some 4-6 digit numbers that don't share a factor with \(30030=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\). Find factors by trial division (Algorithm 12.5.7).

8

Do the same with Fermat Factorization (Algorithm 12.5.10). Try to create a number that takes five steps with Fermat and with trial division.

10

Try using Pollard Rho on a large number you create out of a few big primes (not too big!) with different seeds. Can you get it to take longer than a few turns? Get your prize numbers; now try factoring again with this method where you have changed the polynomial to \(x^3+1\) or something else other than \(x^2+1\).