Number Theory: Lecture 21

In which we learn a little more about solutions to Pell’s equation, and start thinking about primality testing.

Lemma 69: If $(x_1, y_1)$ and $(x_2, y_2)$ are solutions to $x^2 - Ny^2 = 1$ , then so is $(x_1 x_2 + y_1 y_2 N, x_1 y_2 + x_2 y_1)$ . This was a straightforward check (and we managed to avoid doing lots of algebra). So there are infinitely many solutions to Pell’s equation (since we already know that there is one).
Definition of a pseudoprime to the base $b$ .
Lemma 70: If $n$ is pseudoprime to the bases $b_1$ and $b_2$ , then $n$ is pseudoprime to the base $b_1 b_2$ and also to the base $b_1 b_2^{-1}$ . This was easy to check.
Proposition 71: If $n$ is not pseudoprime to some base $b$ , then at least half of all bases are such that $n$ is not pseudoprime to those bases. We showed that there is an injection from {bases to which $n$ is pseudoprime} to {bases to which $n$ is not pseudoprime}.
Definition of a Carmichael number.
Definition of an Euler pseudoprime to the base $b$ .

Preparation for Lecture 22

We finished with the definition of Euler pseudoprimes. It would be helpful to look back over our work today on Fermat pseudoprimes, to see whether you can adapt it to Euler pseudoprimes. I suggest that you start with some examples. Are there analogues of Proposition 71 and of Carmichael numbers for Euler pseudoprimes? You could also think about Carmichael numbers: can you find any? If $n$ is a Carmichael number, what can you say about $n$ and its prime factors?

Like this:

Be the first to like this post.

This entry was posted on November 23, 2011 at 12:20 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Number Theory: Lecture 21”

Number Theory: Lecture 22 « Theorem of the week Says:
November 25, 2011 at 12:27 pm
[...] Theorem of the week Expositions of interesting mathematical results « Number Theory: Lecture 21 [...]

Theorem of the week