Prime Numbers Book

[paulunderwood]

Originally Posted by Nick

There are a number of errors at the start, some just details of definitions but others hiding more important points.
How it would be best to resolve these depends strongly on who you are writing this for.
What is the intended audience?

The man in the street with a little interest in primes and testing

Please detail what the errors are so that I can fix them.

[Nick]

Originally Posted by paulunderwood

The man in the street with a little interest in primes and testing

Please detail what the errors are so that I can fix them.

Feedback on version dated 11 October 2020 (wow you've written a lot!)
p5 The proof that root 2 is irrational relies on the uniqueness of prime factorization.
As this is a special property of the integers (not true in all number systems), I would at least mention it.
p6 Ordinary sets are unordered and may not have repeating elements (this is so that they correspond with properties - if you select all objects satisfying a certain condition, you want what you get to be a set). Orderings and multisets can be constructed from ordinary sets if needed (in fact, so can everything in mathematics).
p6 "subtracting all elements of one set from another" sounds confusing to me, as if you are calculating x-y for each x in the first set and y in the second. I would consider "removing"
p7 The group axioms \(e\circ g=g\) needs to be \(g\circ e=g\), or state it and the next one both ways around.
p7 under multiplication the units of a commutative ring with 1 form an abelian group, but these are not all the elements of the ring (except in the trivial case where the ring has just 1 element).
p8 If you want to be able to relax condition 11 then you need to write condition 12 both ways around!
p8 A field is also required to have 1 not equal to 0.
I'm out of time now - I'll look again in the week.

[paulunderwood]

Originally Posted by Nick

Feedback on version dated 11 October 2020 (wow you've written a lot!)

Thank you very much for taking tome to read the text. I have made some changes to my local copy but will upload after more changes.

p5 The proof that root 2 is irrational relies on the uniqueness of prime factorization.
As this is a special property of the integers (not true in all number systems), I would at least mention it.

.
I mention it now in the both the paragraph on integers and when arguing about the irrationality of root 2.

p6 Ordinary sets are unordered and may not have repeating elements (this is so that they correspond with properties - if you select all objects satisfying a certain condition, you want what you get to be a set). Orderings and multisets can be constructed from ordinary sets if needed (in fact, so can everything in mathematics).

I have added the word "not".

p6 "subtracting all elements of one set from another" sounds confusing to me, as if you are calculating x-y for each x in the first set and y in the second. I would consider "removing"

I replaced the word "subtract" with "remove",

p7 The group axioms \(e\circ g=g\) needs to be \(g\circ e=g\), or state it and the next one both ways around.

I have subtended e rather than prepending it and in all subsequent instances where identity existence in mentioned including the section on rings,

p7 under multiplication the units of a commutative ring with 1 form an abelian group, but these are not all the elements of the ring (except in the trivial case where the ring has just 1 element).

I found this difficult. I have made mention of the center, although it might be out of context:

\item multiplicative identity : $(\exists 1\in {\cal S})(\forall a\in{\cal S})\hspace{.1in}a\times 1=a$.
The units form an Abelian group apart from a ring with one element, called the {\em center}.

p8 If you want to be able to relax condition 11 then you need to write condition 12 both ways around!

Done!

p8 A field is also required to have 1 not equal to 0.

I have added "where $1\ne 0$".

I'm out of time now - I'll look again in the week.

Again, many thanks,

Edit I have uploaded the latest copy -- 12 Oct.

[Nick]

Some feedback on the version dated 12 October 2020:

2.1 Primes.
I find the first sentence confusing (though that may just be me).
Your explanation of what prime numbers are at the start of chapter 1 was clearer.

2.2 Euclid's algorithm
If you are going to use both "greatest common divisor" and "highest common factor",
perhaps saying that they are 2 names for the same thing would make it clearer.
You say the gcd is the last non-zero remainder but don't explain what to do if the 1st remainder was 0 already.
You explain why the last non-zero remainder divides a and b but not why it must be the highest number to do so.

3. Pythagoras
You show that a+b and a-b are both even and that no prime except 2 divides them both,
and you also have that their product is a square.
You conclude that a+b and a-b are each 2 times a square.
But the prime factorizations of a+b and a-b could each contain an even number of 2's
- you need to rule that out as well before writing a+b=2s² and a-b=2t².
(You are of course making it harder for yourself by working in the integers instead of the Gaussian integers here.
As you introduced complex numbers in chapter 1, you could consider using Gaussian integers.)

[paulunderwood]

I have tried to correct and clarify the text and arguments as Nick pointed out in the previous post. I have uploaded the latest version -- Oct 15th, 2020 -- to the original post.

I have not written about Gaussian integers, trying to restrict the text to natural primes,

[Nick]

Feedback on version dated 15 October 2020:

7 Mersenne Numbers
Formula for factorization of \(M_{pq}\) is almost right!

9.1 Legendre symbol
Say p is an odd prime or p not equal to 2.
Typo bottom of page 37: elements of A should go up to 10 instead of 11.

12 Frobenius
Example: taking the polynomial \(x^2+1\), you get the Gaussian integers modulo n after all!

Obviously it's up to you, but it might be worth including something on the Chinese Remainder Theorem.
It would make it easier to explain your formula for the Euler phi function.
Also, as you have a nice emphasis on the computational side of things in this, you could show
how it is used in practice to speed up RSA decryption, for example.
Just a thought, anyway.

[paulunderwood]

Originally Posted by Nick

12 Frobenius
Example: taking the polynomial \(x^2+1\), you get the Gaussian integers modulo n after all!

Obviously it's up to you, but it might be worth including something on the Chinese Remainder Theorem.
It would make it easier to explain your formula for the Euler phi function.
Also, as you have a nice emphasis on the computational side of things in this, you could show
how it is used in practice to speed up RSA decryption, for example.
Just a thought, anyway.

There is now a section on Gaussian primes, but not mod n.

CRT: I find that quite difficult.

RSA: I have written that s or t may be chosen to be small for quick encoding or quick decoding respectively.

Thanks again for your input. 18th Oct, 2020 version uploaded

[a1call]

I love the book Paul.
Thank you very much.