You are browsing as Guest
Click here for list of discussions
Click here to login





Discussion: ThoughtsForABook
You have read-only access
You may need to scroll to the right ...

Click here to view in strict time order
Click here to view in neighbourhood mode.

%3 N_20250420114442a_ColinWright    By ColinWright 2025/04/20 @ 11:44:42a -------------------------------- This is a brain dump of the ideas to cover in a book.        (select only this node)     N_20250420114442b_ColinWright    By ColinWright 2025/04/20 @ 11:44:42b -------------------------------- Not a "popular math" book, nor a "recreational maths" book, but a book that covers some "real maths" in a readable but technically accurate way.        (select only this node)     N_20250420114442a_ColinWright->N_20250420114442b_ColinWright N_20250422152152a_ColinWright    By ColinWright 2025/04/22 @ 15:21:52a -------------------------------- The hook ...        (select only this node)     N_20250420114442a_ColinWright->N_20250422152152a_ColinWright N_20250422162720a_ColinWright    By ColinWright 2025/04/22 @ 16:27:20a -------------------------------- Chapters...        (select only this node)     N_20250420114442a_ColinWright->N_20250422162720a_ColinWright N_20250420114442f_ColinWright    By ColinWright 2025/04/20 @ 11:44:42f -------------------------------- So I'm thinking of "Fermat's theorem on sums of two squares"        (select only this node)     N_20250420114442a_ColinWright->N_20250420114442f_ColinWright N_20250420114442c_ColinWright    By ColinWright 2025/04/20 @ 11:44:42c -------------------------------- Most "Recreational Maths" books are a bit like sweets ... engaging but non-nutritional. I'm wondering if there's space for a book that does some actual maths, while still being readable.        (select only this node)     N_20250420114442b_ColinWright->N_20250420114442c_ColinWright N_20250420213337a_ColinB    By ColinB 2025/04/20 @ 21:33:37a -------------------------------- I shall do my best Katie impersonation and ask "who's the audience?"        (select only this node)     N_20250420114442c_ColinWright->N_20250420213337a_ColinB N_20250420114442d_ColinWright    By ColinWright 2025/04/20 @ 11:44:42d -------------------------------- So I've been inspired by David Acheson's "1089 and All That"        (select only this node)     N_20250420114442c_ColinWright->N_20250420114442d_ColinWright N_20250420114442e_ColinWright    By ColinWright 2025/04/20 @ 11:44:42e -------------------------------- The idea is to start with a hook, trick, game, or puzzle, and end by proving a "Real Theorem"        (select only this node)     N_20250420114442d_ColinWright->N_20250420114442e_ColinWright N_20250420114442e_ColinWright->N_20250422152152a_ColinWright N_20250420114442e_ColinWright->N_20250420114442f_ColinWright N_20250420114717a_ColinWright    By ColinWright 2025/04/20 @ 11:47:17a -------------------------------- Here's a proof. We have two parts to prove:        (select only this node)     N_20250420114442f_ColinWright->N_20250420114717a_ColinWright N_20250420213613a_ColinB    By ColinB 2025/04/20 @ 21:36:13a -------------------------------- I like this from a maths point of view, it's a nice, not-at-all-obvious proposition, and there's plenty of interesting scenery on the journey. Do you have an idea for a hook?        (select only this node)     N_20250420114442f_ColinWright->N_20250420213613a_ColinB N_20250420114442g_ColinWright    By ColinWright 2025/04/20 @ 11:44:42g -------------------------------- https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares        (select only this node)     N_20250420114442f_ColinWright->N_20250420114442g_ColinWright N_20250422104209a_ColinB    By ColinB 2025/04/22 @ 10:42:09a -------------------------------- Related -- there was a G4G gift paper (Hilarie Orman and Rich Schroeppel in 2018, I'm pretty sure) about using something similar to this as a factorisation technique. (If x is the sum of two squares in two different ways, you can Gaussian integer it up to find the factors).        (select only this node)     N_20250420114442g_ColinWright->N_20250422104209a_ColinB N_20250420114717b_ColinWright    By ColinWright 2025/04/20 @ 11:47:17b -------------------------------- If N==3(4) then N is not the sum of two squares        (select only this node)     N_20250420114717a_ColinWright->N_20250420114717b_ColinWright N_20250420114717c_ColinWright    By ColinWright 2025/04/20 @ 11:47:17c -------------------------------- If N==1(4) then N is the sum of two squares        (select only this node)     N_20250420114717a_ColinWright->N_20250420114717c_ColinWright N_20250420115912c_ColinWright    By ColinWright 2025/04/20 @ 11:59:12c -------------------------------- It's hard to show that something *isn't* the sum of two squares because we need to check all the numbers up to that number.        (select only this node)     N_20250420114717b_ColinWright->N_20250420115912c_ColinWright N_20250420115912a_ColinWright    By ColinWright 2025/04/20 @ 11:59:12a -------------------------------- It's interesting that to verify an example ...        (select only this node)     N_20250420114717b_ColinWright->N_20250420115912a_ColinWright N_20250420114930a_ColinWright    By ColinWright 2025/04/20 @ 11:49:30a -------------------------------- Consider N=x^2+y^2 (mod 4)        (select only this node)     N_20250420114717b_ColinWright->N_20250420114930a_ColinWright N_20250420114717c_ColinWright->N_20250420115912a_ColinWright N_20250420115629a_ColinWright    By ColinWright 2025/04/20 @ 11:56:29a -------------------------------- This is (as we know) trickier.        (select only this node)     N_20250420114717c_ColinWright->N_20250420115629a_ColinWright N_20250420121614b_ColinWright    By ColinWright 2025/04/20 @ 12:16:14b -------------------------------- We include 0, and since sqrt(P) is not an integer, the question of whether it's included or not is irrelevant.        (select only this node)     N_20250420114930b_ColinWright    By ColinWright 2025/04/20 @ 11:49:30b -------------------------------- If x and y are both even then ...        (select only this node)     N_20250420114930c_ColinWright    By ColinWright 2025/04/20 @ 11:49:30c -------------------------------- x^2 and y^2 are both 0 (mod 4)        (select only this node)     N_20250420114930b_ColinWright->N_20250420114930c_ColinWright N_20250420114930e_ColinWright    By ColinWright 2025/04/20 @ 11:49:30e -------------------------------- So N is not 3 (mod 4)        (select only this node)     N_20250420115334a_ColinWright    By ColinWright 2025/04/20 @ 11:53:34a -------------------------------- So any odd number that is congruent to 3 (mod 4) is not the sum of two squares.        (select only this node)     N_20250420114930e_ColinWright->N_20250420115334a_ColinWright N_20250420115033a_ColinWright    By ColinWright 2025/04/20 @ 11:50:33a -------------------------------- If x and y are both odd then ...        (select only this node)     N_20250420115033b_ColinWright    By ColinWright 2025/04/20 @ 11:50:33b -------------------------------- x^2 and y^2 are both 1 (mod 4)        (select only this node)     N_20250420115033a_ColinWright->N_20250420115033b_ColinWright N_20250420115033c_ColinWright    By ColinWright 2025/04/20 @ 11:50:33c -------------------------------- So their sum is 2 (mod 4)        (select only this node)     N_20250420115033b_ColinWright->N_20250420115033c_ColinWright N_20250420115033c_ColinWright->N_20250420114930e_ColinWright N_20250420115226a_ColinWright    By ColinWright 2025/04/20 @ 11:52:26a -------------------------------- If one of x and y is even and the other is odd ...        (select only this node)     N_20250420115226b_ColinWright    By ColinWright 2025/04/20 @ 11:52:26b -------------------------------- WLOG x is even and y is odd        (select only this node)     N_20250420115226a_ColinWright->N_20250420115226b_ColinWright N_20250420115226c_ColinWright    By ColinWright 2025/04/20 @ 11:52:26c -------------------------------- Then x^2==0(mod 4) and y^2==1(mod 4)        (select only this node)     N_20250420115226b_ColinWright->N_20250420115226c_ColinWright N_20250420115226d_ColinWright    By ColinWright 2025/04/20 @ 11:52:26d -------------------------------- Hence their sum is 1 (mod 4)        (select only this node)     N_20250420115226c_ColinWright->N_20250420115226d_ColinWright N_20250420115226d_ColinWright->N_20250420114930e_ColinWright N_20250420184050d_ColinWright    By ColinWright 2025/04/20 @ 18:40:50d -------------------------------- Rearrange to get (a-c)=(d-b)u and re-write as A = Bu.        (select only this node)     N_20250420184050e_ColinWright    By ColinWright 2025/04/20 @ 18:40:50e -------------------------------- Observe that A and B are in the range -sqrt(P)...sqrt(P).        (select only this node)     N_20250420184050d_ColinWright->N_20250420184050e_ColinWright N_20250420184341a_ColinWright    By ColinWright 2025/04/20 @ 18:43:41a -------------------------------- Square both sides: A^2=B^2u^2        (select only this node)     N_20250420184050d_ColinWright->N_20250420184341a_ColinWright N_20250420122231b_ColinWright    By ColinWright 2025/04/20 @ 12:22:31b -------------------------------- So in total, we have [floor(sqrt(P))+1]^2 values.        (select only this node)     N_20250420122231c_ColinWright    By ColinWright 2025/04/20 @ 12:22:31c -------------------------------- That is strictly bigger than P.        (select only this node)     N_20250420122231b_ColinWright->N_20250420122231c_ColinWright N_20250420115554a_ColinWright    By ColinWright 2025/04/20 @ 11:55:54a -------------------------------- This can all be made a lot slicker and simpler if the reader has some experience of and practice with modular arithmetic.        (select only this node)     N_20250420115334a_ColinWright->N_20250420115554a_ColinWright N_20250420120848a_ColinWright    By ColinWright 2025/04/20 @ 12:08:48a -------------------------------- So how do we do this.        (select only this node)     N_20250420115629a_ColinWright->N_20250420120848a_ColinWright N_20250420184341c_ColinWright    By ColinWright 2025/04/20 @ 18:43:41c -------------------------------- But u^2=-1, so this is A^2 = -(B^2)        (select only this node)     N_20250420184341a_ColinWright->N_20250420184341c_ColinWright N_20250420184341b_ColinWright    By ColinWright 2025/04/20 @ 18:43:41b -------------------------------- (Remember this is all modulo P)        (select only this node)     N_20250420184341a_ColinWright->N_20250420184341b_ColinWright N_20250420115912b_ColinWright    By ColinWright 2025/04/20 @ 11:59:12b -------------------------------- It's easy to show that something *is* the sum of two squares, we simply show the squares        (select only this node)     N_20250420115912a_ColinWright->N_20250420115912b_ColinWright N_20250420115912a_ColinWright->N_20250420115912c_ColinWright N_20250420115912e_ColinWright    By ColinWright 2025/04/20 @ 11:59:12e -------------------------------- It's easy to prove something *can't* be the sum of two squares by using the mod 4 argument        (select only this node)     N_20250420115912c_ColinWright->N_20250420115912e_ColinWright N_20250420115912d_ColinWright    By ColinWright 2025/04/20 @ 11:59:12d -------------------------------- But        (select only this node)     N_20250420115912c_ColinWright->N_20250420115912d_ColinWright N_20250420184341g_ColinWright    By ColinWright 2025/04/20 @ 18:43:41g -------------------------------- It can't be zero.        (select only this node)     N_20250420184341i_ColinWright    By ColinWright 2025/04/20 @ 18:43:41i -------------------------------- So it must be P.        (select only this node)     N_20250420184341g_ColinWright->N_20250420184341i_ColinWright N_20250420115912d_ColinWright->N_20250420115912e_ColinWright N_20250420115912f_ColinWright    By ColinWright 2025/04/20 @ 11:59:12f -------------------------------- It's harder to show something always *is* the sum of two squares. It's a tricky proof.        (select only this node)     N_20250420115912d_ColinWright->N_20250420115912f_ColinWright N_20250420115912f_ColinWright->N_20250420120848a_ColinWright N_20250420120848b_ColinWright    By ColinWright 2025/04/20 @ 12:08:48b -------------------------------- Here's a proof.        (select only this node)     N_20250420120848a_ColinWright->N_20250420120848b_ColinWright N_20250420120848d_ColinWright    By ColinWright 2025/04/20 @ 12:08:48d -------------------------------- Let's start with a prime number P that is 4k+1.        (select only this node)     N_20250420120848b_ColinWright->N_20250420120848d_ColinWright N_20250420120848c_ColinWright    By ColinWright 2025/04/20 @ 12:08:48c -------------------------------- The idea is that all these concepts will have been introduced and discussed as stand-alone, interesting chapters, so this is a coming together of multiple ideas.        (select only this node)     N_20250420120848b_ColinWright->N_20250420120848c_ColinWright N_20250420191327a_ColinWright    By ColinWright 2025/04/20 @ 19:13:27a -------------------------------- We have choices to make here, let's choose a less obvious one in each case        (select only this node)     N_20250420191327c_ColinWright    By ColinWright 2025/04/20 @ 19:13:27c -------------------------------- Let's choose repeated value 22: 5+1*17 == 0+3*17 (mod 29)        (select only this node)     N_20250420191327a_ColinWright->N_20250420191327c_ColinWright N_20250420191327b_ColinWright    By ColinWright 2025/04/20 @ 19:13:27b -------------------------------- Let's choose repeated value 3: 3+0*5 == 1+3*5 (mod 13)        (select only this node)     N_20250420191327a_ColinWright->N_20250420191327b_ColinWright N_20250420120848e_ColinWright    By ColinWright 2025/04/20 @ 12:08:48e -------------------------------- We'll use two running examples: 13 and 29        (select only this node)     N_20250420120848d_ColinWright->N_20250420120848e_ColinWright N_20250420120848f_ColinWright    By ColinWright 2025/04/20 @ 12:08:48f -------------------------------- We know from chapter U that -1 has a square root (mod P)        (select only this node)     N_20250420120848d_ColinWright->N_20250420120848f_ColinWright N_20250420121118b_ColinWright    By ColinWright 2025/04/20 @ 12:11:18b -------------------------------- 17^2=-1 (mod 29)        (select only this node)     N_20250420120848e_ColinWright->N_20250420121118b_ColinWright N_20250420121118a_ColinWright    By ColinWright 2025/04/20 @ 12:11:18a -------------------------------- 5^2=-1 (mod 13)        (select only this node)     N_20250420120848e_ColinWright->N_20250420121118a_ColinWright N_20250420120848g_ColinWright    By ColinWright 2025/04/20 @ 12:08:48g -------------------------------- So there is a number, u, such that u^2=-1 (mod P)        (select only this node)     N_20250420120848f_ColinWright->N_20250420120848g_ColinWright N_20250420121431a_ColinWright    By ColinWright 2025/04/20 @ 12:14:31a -------------------------------- What we do now is a standard trick that we might recognise from the discussion about GCDs and Euclid's Algorithm.        (select only this node)     N_20250420120848g_ColinWright->N_20250420121431a_ColinWright N_20250420121809b_ColinWright    By ColinWright 2025/04/20 @ 12:18:09b -------------------------------- So we use u=17        (select only this node)     N_20250420121118b_ColinWright->N_20250420121809b_ColinWright N_20250420121118c_ColinWright    By ColinWright 2025/04/20 @ 12:11:18c -------------------------------- You can check these numerically ... the "negatives" will also work, as we saw in Chapter U.        (select only this node)     N_20250420121118b_ColinWright->N_20250420121118c_ColinWright N_20250420192446a_ColinWright    By ColinWright 2025/04/20 @ 19:24:46a -------------------------------- So (5-0)==(3-1)*17 (mod 29)        (select only this node)     N_20250420191327c_ColinWright->N_20250420192446a_ColinWright N_20250420121118c_ColinWright->N_20250420121809b_ColinWright N_20250420121809a_ColinWright    By ColinWright 2025/04/20 @ 12:18:09a -------------------------------- So we use u=5        (select only this node)     N_20250420121118c_ColinWright->N_20250420121809a_ColinWright N_20250420121431b_ColinWright    By ColinWright 2025/04/20 @ 12:14:31b -------------------------------- Consider all numbers of the form a+bu, where a and b lie in some range.        (select only this node)     N_20250420121431a_ColinWright->N_20250420121431b_ColinWright N_20250420121431c_ColinWright    By ColinWright 2025/04/20 @ 12:14:31c -------------------------------- This is a clever step! It requires lots of experience, and a little inspiration, both of which can come simply from playing with things.        (select only this node)     N_20250420121431b_ColinWright->N_20250420121431c_ColinWright N_20250420121614a_ColinWright    By ColinWright 2025/04/20 @ 12:16:14a -------------------------------- The range we use is for a and b to lie between 0 and sqrt(P).        (select only this node)     N_20250420121431b_ColinWright->N_20250420121614a_ColinWright N_20250420121431c_ColinWright->N_20250420121614a_ColinWright N_20250420122735a_ColinWright    By ColinWright 2025/04/20 @ 12:27:35a -------------------------------- P=13, so a and b can each takes the values 0, 1, 2, and 3.        (select only this node)     N_20250420121614a_ColinWright->N_20250420122735a_ColinWright N_20250420122231a_ColinWright    By ColinWright 2025/04/20 @ 12:22:31a -------------------------------- Counting carefully we see that each of a and b can take floor(sqrt(P))+1 values.        (select only this node)     N_20250420121614a_ColinWright->N_20250420122231a_ColinWright N_20250420122735b_ColinWright    By ColinWright 2025/04/20 @ 12:27:35b -------------------------------- P=29, so a and b can each takes the values 0, 1, 2, 3, 4, and 5.        (select only this node)     N_20250420121614a_ColinWright->N_20250420122735b_ColinWright N_20250420121614a_ColinWright->N_20250420121614b_ColinWright N_20250420121809a_ColinWright->N_20250420122735a_ColinWright N_20250420192859a_ColinWright    By ColinWright 2025/04/20 @ 19:28:59a -------------------------------- We could equally well use u=-5 which is the same as u=8 (mod 13)        (select only this node)     N_20250420121809a_ColinWright->N_20250420192859a_ColinWright N_20250420121809b_ColinWright->N_20250420122735b_ColinWright N_20250420192835a_ColinWright    By ColinWright 2025/04/20 @ 19:28:35a -------------------------------- We could equally well use u=-17 which is the same as u=12 (mod 29)        (select only this node)     N_20250420121809b_ColinWright->N_20250420192835a_ColinWright N_20250420192251a_ColinWright    By ColinWright 2025/04/20 @ 19:22:51a -------------------------------- So (3-1)==(3-0)*5 (mod 13)        (select only this node)     N_20250420192251b_ColinWright    By ColinWright 2025/04/20 @ 19:22:51b -------------------------------- 2==3*5        (select only this node)     N_20250420192251a_ColinWright->N_20250420192251b_ColinWright N_20250420122231a_ColinWright->N_20250420122231b_ColinWright N_20250420184050a_ColinWright    By ColinWright 2025/04/20 @ 18:40:50a -------------------------------- So now we have all these possible values for a+bu(mod P). They are just numbers in the range 0..(P-1). And there are more than P of them.        (select only this node)     N_20250420122231c_ColinWright->N_20250420184050a_ColinWright N_20250420191327b_ColinWright->N_20250420192251a_ColinWright N_20250420190525a_ColinWright    By ColinWright 2025/04/20 @ 19:05:25a -------------------------------- b = : 0 1  2 3 ----+--------- a=0 : 0 5 10 2 a=1 : 1 6 11 3 a=2 : 2 7 12 4 a=3 : 3 8  0 5        (select only this node)     N_20250420122735a_ColinWright->N_20250420190525a_ColinWright N_20250420190851a_ColinWright    By ColinWright 2025/04/20 @ 19:08:51a -------------------------------- b =  : 0  1  2  3  4  5 -----+----------------- a= 0 : 0 17  5 22 10 27 a= 1 : 1 18  6 23 11 28 a= 2 : 2 19  7 24 12  0 a= 3 : 3 20  8 25 13  1 a= 4 : 4 21  9 26 14  2 a= 5 : 5 22 10 27 15  3        (select only this node)     N_20250420122735b_ColinWright->N_20250420190851a_ColinWright N_20250420192251c_ColinWright    By ColinWright 2025/04/20 @ 19:22:51c -------------------------------- 2^2 == 3^2 * 5^2 (mod 13)        (select only this node)     N_20250420192251b_ColinWright->N_20250420192251c_ColinWright N_20250420184050b_ColinWright    By ColinWright 2025/04/20 @ 18:40:50b -------------------------------- So by the Pigeon-Hole principle (See Chapter P) we must have some repeats.        (select only this node)     N_20250420184050a_ColinWright->N_20250420184050b_ColinWright N_20250420184050b_ColinWright->N_20250420191327a_ColinWright N_20250420184050c_ColinWright    By ColinWright 2025/04/20 @ 18:40:50c -------------------------------- So we have a+bu=c+du (mod P), where a=/=c or b=/=d or both.        (select only this node)     N_20250420184050b_ColinWright->N_20250420184050c_ColinWright N_20250420184050c_ColinWright->N_20250420184050d_ColinWright N_20250420192251d_ColinWright    By ColinWright 2025/04/20 @ 19:22:51d -------------------------------- 4 == 9 * (-1) (mod 13)        (select only this node)     N_20250420192251c_ColinWright->N_20250420192251d_ColinWright N_20250420184341d_ColinWright    By ColinWright 2025/04/20 @ 18:43:41d -------------------------------- That means A^2+B^2 = 0        (select only this node)     N_20250420184341c_ColinWright->N_20250420184341d_ColinWright N_20250420184341f_ColinWright    By ColinWright 2025/04/20 @ 18:43:41f -------------------------------- So A^2+B^2 is a multiple of P. (Now no longer working mod P)        (select only this node)     N_20250420184341d_ColinWright->N_20250420184341f_ColinWright N_20250420184341e_ColinWright    By ColinWright 2025/04/20 @ 18:43:41e -------------------------------- (Modulo P)        (select only this node)     N_20250420184341d_ColinWright->N_20250420184341e_ColinWright N_20250420192251e_ColinWright    By ColinWright 2025/04/20 @ 19:22:51e -------------------------------- 4 == -9 (mod 13)        (select only this node)     N_20250420192251d_ColinWright->N_20250420192251e_ColinWright N_20250420184341h_ColinWright    By ColinWright 2025/04/20 @ 18:43:41h -------------------------------- It can't be as big as 2P        (select only this node)     N_20250420184341f_ColinWright->N_20250420184341h_ColinWright N_20250420184341f_ColinWright->N_20250420184341g_ColinWright N_20250420184341h_ColinWright->N_20250420184341i_ColinWright N_20250420184341j_ColinWright    By ColinWright 2025/04/20 @ 18:43:41j -------------------------------- Hence A^2+B^2 = P        (select only this node)     N_20250420184341i_ColinWright->N_20250420184341j_ColinWright N_20250420190525a_ColinWright->N_20250420191327a_ColinWright N_20250420190525a_ColinWright->N_20250420191327b_ColinWright N_20250420192251f_ColinWright    By ColinWright 2025/04/20 @ 19:22:51f -------------------------------- 4 + 9 == 0 (mod 13)        (select only this node)     N_20250420192251e_ColinWright->N_20250420192251f_ColinWright N_20250420114930a_ColinWright->N_20250420115033a_ColinWright N_20250420114930a_ColinWright->N_20250420114930b_ColinWright N_20250420114930a_ColinWright->N_20250420115226a_ColinWright N_20250420192251g_ColinWright    By ColinWright 2025/04/20 @ 19:22:51g -------------------------------- 4 + 9 = 13        (select only this node)     N_20250420192251f_ColinWright->N_20250420192251g_ColinWright N_20250420114930d_ColinWright    By ColinWright 2025/04/20 @ 11:49:30d -------------------------------- So their sum is 0 (mod 4)        (select only this node)     N_20250420114930c_ColinWright->N_20250420114930d_ColinWright N_20250420115912b_ColinWright->N_20250420115912d_ColinWright N_20250420115912b_ColinWright->N_20250420115912f_ColinWright N_20250420114930d_ColinWright->N_20250420114930e_ColinWright N_20250420190851a_ColinWright->N_20250420191327c_ColinWright N_20250420190851a_ColinWright->N_20250420191327a_ColinWright N_20250420192446b_ColinWright    By ColinWright 2025/04/20 @ 19:24:46b -------------------------------- 5==2*17 (mod 29)        (select only this node)     N_20250420192446a_ColinWright->N_20250420192446b_ColinWright N_20250420121118a_ColinWright->N_20250420121809a_ColinWright N_20250420121118a_ColinWright->N_20250420121118c_ColinWright N_20250420213337a_ColinB->N_20250420213613a_ColinB N_20250420214301a_ColinWright    By ColinWright 2025/04/20 @ 21:43:01a -------------------------------- Yes. My neighbour has a degree in chemistry and is interested in the maths I talk about, but A-Level was a long time ago and wasn't his subject. So I'm aiming it at him, and therefore should cover the mythical interested 14 to 16-year-old.        (select only this node)     N_20250420213337a_ColinB->N_20250420214301a_ColinWright N_20250420192446c_ColinWright    By ColinWright 2025/04/20 @ 19:24:46c -------------------------------- 5^2 == 2^2 * 17^2 (mod 29)        (select only this node)     N_20250420192446b_ColinWright->N_20250420192446c_ColinWright N_20250422170414a_ColinWright    By ColinWright 2025/04/22 @ 17:04:14a -------------------------------- Pollard Rho        (select only this node)     N_20250422154633a_ColinWright    By ColinWright 2025/04/22 @ 15:46:33a -------------------------------- So the question is ...        (select only this node)     N_20250422154633b_ColinWright    By ColinWright 2025/04/22 @ 15:46:33b -------------------------------- Does this pattern go forever?        (select only this node)     N_20250422154633a_ColinWright->N_20250422154633b_ColinWright N_20250422152152f_ColinWright    By ColinWright 2025/04/22 @ 15:21:52f -------------------------------- (Cannot be written as a times b with both a>1 and b>1)        (select only this node)     N_20250422180345a_ColinWright    By ColinWright 2025/04/22 @ 18:03:45a -------------------------------- We can generate these with the Sieve or Eratosthenes        (select only this node)     N_20250422152152f_ColinWright->N_20250422180345a_ColinWright N_20250422162720e_ColinWright    By ColinWright 2025/04/22 @ 16:27:20e -------------------------------- Modulo arithmetic        (select only this node)     N_20250422162720i_ColinWright    By ColinWright 2025/04/22 @ 16:27:20i -------------------------------- Factoring Integers        (select only this node)     N_20250422162720e_ColinWright->N_20250422162720i_ColinWright N_20250422164316a_ColinWright    By ColinWright 2025/04/22 @ 16:43:16a -------------------------------- Semi-Modern Cryptography        (select only this node)     N_20250422162720e_ColinWright->N_20250422164316a_ColinWright N_20250422170733a_ColinWright    By ColinWright 2025/04/22 @ 17:07:33a -------------------------------- Birthday "Paradox" on Jupiter        (select only this node)     N_20250422170733a_ColinWright->N_20250422170414a_ColinWright N_20250422162720k_ColinWright    By ColinWright 2025/04/22 @ 16:27:20k -------------------------------- Matrix Multiplication        (select only this node)     N_20250422163945a_ColinWright    By ColinWright 2025/04/22 @ 16:39:45a -------------------------------- Fibonacci numbers        (select only this node)     N_20250422162720k_ColinWright->N_20250422163945a_ColinWright N_20250422162720c_ColinWright    By ColinWright 2025/04/22 @ 16:27:20c -------------------------------- Perrin Pseudo-primes        (select only this node)     N_20250422162720k_ColinWright->N_20250422162720c_ColinWright N_20250420192446d_ColinWright    By ColinWright 2025/04/20 @ 19:24:46d -------------------------------- 25 == 4 * (-1) (mod 29)        (select only this node)     N_20250420192446c_ColinWright->N_20250420192446d_ColinWright N_20250422162720l_ColinWright    By ColinWright 2025/04/22 @ 16:27:20l -------------------------------- Ancient Egyptian multiplication        (select only this node)     N_20250422162720l_ColinWright->N_20250422162720k_ColinWright N_20250422172732a_ColinWright    By ColinWright 2025/04/22 @ 17:27:32a -------------------------------- Modern cryptography now uses Elliptic Curves, but it's pretty much identical to these techniques, just on a different group!        (select only this node)     N_20250420192446e_ColinWright    By ColinWright 2025/04/20 @ 19:24:46e -------------------------------- 25 == -4 (mod 29)        (select only this node)     N_20250420192446d_ColinWright->N_20250420192446e_ColinWright N_20250420214822a_ColinWright    By ColinWright 2025/04/20 @ 21:48:22a -------------------------------- As a cautionary tale, have a diversion into the Perrin Pseudo-Primes and see that it fails for N=270441. So small examples aren't enough.        (select only this node)     N_20250422162720c_ColinWright->N_20250420214822a_ColinWright N_20250422162720f_ColinWright    By ColinWright 2025/04/22 @ 16:27:20f -------------------------------- Multiplicative Inverses        (select only this node)     N_20250422162720g_ColinWright    By ColinWright 2025/04/22 @ 16:27:20g -------------------------------- Group Theory        (select only this node)     N_20250422162720f_ColinWright->N_20250422162720g_ColinWright N_20250422162720d_ColinWright    By ColinWright 2025/04/22 @ 16:27:20d -------------------------------- Wilson's Theorem        (select only this node)     N_20250422162720f_ColinWright->N_20250422162720d_ColinWright N_20250422162720i_ColinWright->N_20250422170414a_ColinWright N_20250422163945a_ColinWright->N_20250422162720c_ColinWright N_20250422174035d_ColinWright    By ColinWright 2025/04/22 @ 17:40:35d -------------------------------- Fermat's Little Theorem        (select only this node)     N_20250420192446f_ColinWright    By ColinWright 2025/04/20 @ 19:24:46f -------------------------------- 25 + 4 == 0 (mod 29)        (select only this node)     N_20250420192446g_ColinWright    By ColinWright 2025/04/20 @ 19:24:46g -------------------------------- 25 + 4 = 29        (select only this node)     N_20250420192446f_ColinWright->N_20250420192446g_ColinWright N_20250422162720h_ColinWright    By ColinWright 2025/04/22 @ 16:27:20h -------------------------------- Square root of minus 1        (select only this node)     N_20250422164935b_ColinWright    By ColinWright 2025/04/22 @ 16:49:35b -------------------------------- Does not exist mod p if p=4k+3        (select only this node)     N_20250422162720h_ColinWright->N_20250422164935b_ColinWright N_20250422164935a_ColinWright    By ColinWright 2025/04/22 @ 16:49:35a -------------------------------- Exists mod p if p=4k+1        (select only this node)     N_20250422162720h_ColinWright->N_20250422164935a_ColinWright N_20250422164316b_ColinWright    By ColinWright 2025/04/22 @ 16:43:16b -------------------------------- DHMW        (select only this node)     N_20250422164316a_ColinWright->N_20250422164316b_ColinWright N_20250422164316c_ColinWright    By ColinWright 2025/04/22 @ 16:43:16c -------------------------------- RSA        (select only this node)     N_20250422164316a_ColinWright->N_20250422164316c_ColinWright N_20250420192446e_ColinWright->N_20250420192446f_ColinWright N_20250420213613a_ColinB->N_20250422152152a_ColinWright N_20250422174035a_ColinWright    By ColinWright 2025/04/22 @ 17:40:35a -------------------------------- Fermat        (select only this node)     N_20250422174035b_ColinWright    By ColinWright 2025/04/22 @ 17:40:35b -------------------------------- Fermat Factoring        (select only this node)     N_20250422174035a_ColinWright->N_20250422174035b_ColinWright N_20250422174035a_ColinWright->N_20250422174035d_ColinWright N_20250422174035b_ColinWright->N_20250422162720i_ColinWright N_20250422174035c_ColinWright    By ColinWright 2025/04/22 @ 17:40:35c -------------------------------- Difference of two squares        (select only this node)     N_20250422174035c_ColinWright->N_20250422174035b_ColinWright N_20250420214822b_ColinWright    By ColinWright 2025/04/20 @ 21:48:22b -------------------------------- Then go into Wilson's theorem, which feels similar(ish), but which *does* work.        (select only this node)     N_20250420214822a_ColinWright->N_20250420214822b_ColinWright N_20250420214822c_ColinWright    By ColinWright 2025/04/20 @ 21:48:22c -------------------------------- That requires a diversion into some simple group theory, which I then end up using later to show that for primes congruent to 3 mod 4, -1 is not a quadratic residue.        (select only this node)     N_20250420214822b_ColinWright->N_20250420214822c_ColinWright N_20250420214822d_ColinWright    By ColinWright 2025/04/20 @ 21:48:22d -------------------------------- So the web of chapters feels quite nice.        (select only this node)     N_20250420214822c_ColinWright->N_20250420214822d_ColinWright N_20250422103628a_ColinB    By ColinB 2025/04/22 @ 10:36:28a -------------------------------- Agreed -- something I like about this is there's a sense of flailing about and *discovering* the solution rather than being presented it.        (select only this node)     N_20250420214822d_ColinWright->N_20250422103628a_ColinB N_20250422103701a_ColinB    By ColinB 2025/04/22 @ 10:37:01a -------------------------------- The more "go and play with this! What can you figure out?" there is, the better.        (select only this node)     N_20250422103628a_ColinB->N_20250422103701a_ColinB N_20250422103753a_ColinB    By ColinB 2025/04/22 @ 10:37:53a -------------------------------- Part of me wonders about a choose-your-own-adventure sort of thing.        (select only this node)     N_20250422103701a_ColinB->N_20250422103753a_ColinB N_20250422105619a_ColinWright    By ColinWright 2025/04/22 @ 10:56:19a -------------------------------- This is something I was wondering ... have multiple paths through the book and allow people to follow their noses (and interests), with back-references to go back and fill in the gaps.        (select only this node)     N_20250422103753a_ColinB->N_20250422105619a_ColinWright N_20250422104606a_ColinB    By ColinB 2025/04/22 @ 10:46:06a -------------------------------- E.g. 485 is 22^2 + 1^2 and 17^2 + 14^2, and (22+i)(17+14i) = 360+325i -- or 5(72 + 65i). 72^2 + 65^2 = 97^2, and 97 is the other factor.        (select only this node)     N_20250422104209a_ColinB->N_20250422104606a_ColinB N_20250422110227a_ColinWright    By ColinWright 2025/04/22 @ 11:02:27a -------------------------------- Oh, I like that. There are lots of connections to factoring throughout the entire web of topics, and that, of course, relates to cryptography.        (select only this node)     N_20250422104606a_ColinB->N_20250422110227a_ColinWright N_20250422110227b_ColinWright    By ColinWright 2025/04/22 @ 11:02:27b -------------------------------- There is definitely a danger of having too much to put in one book ...        (select only this node)     N_20250422110227a_ColinWright->N_20250422110227b_ColinWright N_20250422152152b_ColinWright    By ColinWright 2025/04/22 @ 15:21:52b -------------------------------- Let me tell you a story that's not real.        (select only this node)     N_20250422152152a_ColinWright->N_20250422152152b_ColinWright N_20250422152152c_ColinWright    By ColinWright 2025/04/22 @ 15:21:52c -------------------------------- When I was younger I knew about Pythagoras        (select only this node)     N_20250422152152b_ColinWright->N_20250422152152c_ColinWright N_20250422152152e_ColinWright    By ColinWright 2025/04/22 @ 15:21:52e -------------------------------- ... and I knew about prime numbers        (select only this node)     N_20250422152152c_ColinWright->N_20250422152152e_ColinWright N_20250422152152d_ColinWright    By ColinWright 2025/04/22 @ 15:21:52d -------------------------------- (a^2+b^2=c^2)        (select only this node)     N_20250422152152c_ColinWright->N_20250422152152d_ColinWright N_20250422152152g_ColinWright    By ColinWright 2025/04/22 @ 15:21:52g -------------------------------- ... and I kinda mixed them up. I wondered if I could write p=a^2+b^2        (select only this node)     N_20250422152152e_ColinWright->N_20250422152152g_ColinWright N_20250422152152e_ColinWright->N_20250422152152f_ColinWright N_20250422152152h_ColinWright    By ColinWright 2025/04/22 @ 15:21:52h -------------------------------- So given an odd prime p (ignoring 2) I said:        (select only this node)     N_20250422152152g_ColinWright->N_20250422152152h_ColinWright N_20250422152152i_ColinWright    By ColinWright 2025/04/22 @ 15:21:52i -------------------------------- If p can be written as a^2+b^2 then I'll colour it Green        (select only this node)     N_20250422153355a_ColinWright    By ColinWright 2025/04/22 @ 15:33:55a -------------------------------- So the following are Green primes:        (select only this node)     N_20250422152152i_ColinWright->N_20250422153355a_ColinWright N_20250422152152j_ColinWright    By ColinWright 2025/04/22 @ 15:21:52j -------------------------------- If p cannot be written as a^2+b^2 then I'll colour it Red        (select only this node)     N_20250422153447a_ColinWright    By ColinWright 2025/04/22 @ 15:34:47a -------------------------------- So the following are Red primes:        (select only this node)     N_20250422152152j_ColinWright->N_20250422153447a_ColinWright N_20250422153355b_ColinWright    By ColinWright 2025/04/22 @ 15:33:55b -------------------------------- Green: 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, ...        (select only this node)     N_20250422153355a_ColinWright->N_20250422153355b_ColinWright N_20250422153903a_ColinWright    By ColinWright 2025/04/22 @ 15:39:03a -------------------------------- When I take the difference of any two Green primes, the difference is always a multiple of 4.        (select only this node)     N_20250422153355b_ColinWright->N_20250422153903a_ColinWright N_20250422153833a_ColinWright    By ColinWright 2025/04/22 @ 15:38:33a -------------------------------- Initially there doesn't seem to be any pattern. But then I noticed:        (select only this node)     N_20250422153355b_ColinWright->N_20250422153833a_ColinWright N_20250422153447b_ColinWright    By ColinWright 2025/04/22 @ 15:34:47b -------------------------------- Red: 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, ...        (select only this node)     N_20250422153942a_ColinWright    By ColinWright 2025/04/22 @ 15:39:42a -------------------------------- When I take the difference of any two Red primes, the difference is always a multiple of 4.        (select only this node)     N_20250422153447b_ColinWright->N_20250422153942a_ColinWright N_20250422153447b_ColinWright->N_20250422153833a_ColinWright N_20250422163650a_ColinWright    By ColinWright 2025/04/22 @ 16:36:50a -------------------------------- Lagrange's Theorem        (select only this node)     N_20250422163650a_ColinWright->N_20250422174035d_ColinWright N_20250422163650a_ColinWright->N_20250422162720h_ColinWright N_20250422163650a_ColinWright->N_20250422164935b_ColinWright N_20250422153447a_ColinWright->N_20250422153447b_ColinWright N_20250422164316b_ColinWright->N_20250422172732a_ColinWright N_20250422152152h_ColinWright->N_20250422152152j_ColinWright N_20250422152152h_ColinWright->N_20250422152152i_ColinWright N_20250422153833a_ColinWright->N_20250422153942a_ColinWright N_20250422153833a_ColinWright->N_20250422153903a_ColinWright N_20250422154059a_ColinWright    By ColinWright 2025/04/22 @ 15:40:59a -------------------------------- So far, Green primes are always 4k+1        (select only this node)     N_20250422153903a_ColinWright->N_20250422154059a_ColinWright N_20250422154035a_ColinWright    By ColinWright 2025/04/22 @ 15:40:35a -------------------------------- So far, Red primes are always 4k+3        (select only this node)     N_20250422153942a_ColinWright->N_20250422154035a_ColinWright N_20250422154035a_ColinWright->N_20250422154633a_ColinWright N_20250422154059a_ColinWright->N_20250422154633a_ColinWright N_20250422164316c_ColinWright->N_20250422172732a_ColinWright N_20250422154633c_ColinWright    By ColinWright 2025/04/22 @ 15:46:33c -------------------------------- Stand by for a cautionary tale ...        (select only this node)     N_20250422155437a_ColinWright    By ColinWright 2025/04/22 @ 15:54:37a -------------------------------- Perrin sequence and pseudo-primes        (select only this node)     N_20250422154633c_ColinWright->N_20250422155437a_ColinWright N_20250422155437a_ColinWright->N_20250422162720c_ColinWright N_20250422164935a_ColinWright->N_20250420120848f_ColinWright N_20250422154633b_ColinWright->N_20250422154633c_ColinWright N_20250422162720a_ColinWright->N_20250420114442f_ColinWright N_20250422162720b_ColinWright    By ColinWright 2025/04/22 @ 16:27:20b -------------------------------- The Hook: Pythagoras/Primes Mash-up        (select only this node)     N_20250422162720a_ColinWright->N_20250422162720b_ColinWright N_20250422162720a_ColinWright->N_20250422170733a_ColinWright N_20250422162720a_ColinWright->N_20250422174035a_ColinWright N_20250422162720j_ColinWright    By ColinWright 2025/04/22 @ 16:27:20j -------------------------------- Euclid's Algorithm        (select only this node)     N_20250422162720b_ColinWright->N_20250422162720j_ColinWright N_20250422170235a_ColinWright    By ColinWright 2025/04/22 @ 17:02:35a -------------------------------- Pigeon-Hole Principle        (select only this node)     N_20250422162720b_ColinWright->N_20250422170235a_ColinWright N_20250422162720b_ColinWright->N_20250422162720k_ColinWright N_20250422162720b_ColinWright->N_20250422152152a_ColinWright N_20250422162720b_ColinWright->N_20250422162720e_ColinWright N_20250422162720b_ColinWright->N_20250422162720l_ColinWright N_20250422162720d_ColinWright->N_20250422162720h_ColinWright N_20250422162720d_ColinWright->N_20250422164935a_ColinWright N_20250422162720g_ColinWright->N_20250422163650a_ColinWright N_20250422162720g_ColinWright->N_20250422172732a_ColinWright N_20250422162720j_ColinWright->N_20250422162720f_ColinWright N_20250422170235a_ColinWright->N_20250422170414a_ColinWright N_20250422170235a_ColinWright->N_20250420184050b_ColinWright