Physicist: We occasionally get questions about free learning resources. Khan academy is excellent, and if you poke around you can find a smattering of free class notes and text books, but generally speaking the more more detailed/advanced the material, the more difficult it is to find/understand.
In keeping with that tradition, here’s this ↓. It was originally written for a group of “mathlete” high school students to teach them number theory and erode their egos a bit. It’s Socratic, so rather than just presenting stuff to be known, it’s mostly a series of leading questions.
Although number theory is a huge, horrifying field, what’s presented here is fairly accessible. If you’re comfortable with arithmetic and have patience and time and paper, you can work through this (but keep in mind, it’s not supposed to be easy). Most of the problems benefit from making up an example or two.
If you notice any typos or omissions, or have questions or answers, put that mess in the comments, and if you happen to be a fair hand at LaTex and feel like constructing some solutions, I’ll post the hell out of that.
Part 1: In which Euclid’s algorithm is considered and linear Diophantine equations are seen to be over-named.
Part 2: In which modular arithmetic is shown to be easier than regular arithmetic and primes are counted and accounted for.
Part 3: Wherein modular arithmetic is shown to be harder than was previously implied, Wilson’s theorem is briefly noted, and divisor functions are dissected.
Part 4: Whereby Euler’s theorem is revealed to high praise, and Fermat’s little theorem is proposed as an after-thought.
Part 5: That the hidden structures of modular math might better be understood, Professor Emeritus Chinese’s invaluable Chinese Remainder Theorem is revealed.
Part 6: The end of this short and arduous journey of discovery finds us face to face with RSA encryption, which is now seen as it truly is; no biggie.
Update: The Gang of Five came up with these solutions for part 1.
where are the answers to each of the 6 parts?
Never got around to typing that up.
Everything does have an answer though.
I’m inspired to apply computational physics to RSA for an end of class project due in May. I’m yet uncertain as to how I will relate the topics, but it appears that this article may prove a valuable resource as a lead up to the material. I’ve started your first assignment and have begun making revisions/adding solutions.
Where are the .tex’s made available?
First of all i apologize for my poor English.
Hi, the specifications are… (everything is demostrated):
if you´re interesting in this demostration or know some adresses where they could help me, send me a email to miguelangelreybonet@yahoo.es thank you.
1. if p=1 (mod 4) then c= – 1
if p=3 (mod 8) then c= – 2
if p=7 (mod 8) then c= +2
then with p odd number and p>0
then:
2 if p is prime (irreductible of Z) then b exist in (1,p-1) / b^2= c (mod p)
(ONLY exist +- b)
then: p= x^2 – c*y^2 and not exist x´ and y´/ p not= x¨^2 -c*y^2
(x odd number always and: y pair if p=1 (mod 4) & y odd if p = 3 (mod 4) )
3 if p is not prime (not irreductible of Z) then
3.1. not exist p=x^2 – c*y^2
3.2. exist p=x^2 – c*y^2=x´^2 – c*y´^2=…..=x´´´´^2 – c*y´´´´^2=…. (with limit)
and exist b1,b2,b3,….,bn / ni^2=c (mod p)
3.3. exist p=x^2 – c*y^2 not exist x´, y´,…,x´´´´,y´´´´,…..
then p = q^2 (not prime)
OR not exist b / in Z/p: x^2=c*y^2 (mod p) <=>
x = +- b*y (mod p) / (b^2) not= c (mod p) not exist m in (1,p-1) /
m^2 not=c (mod p)
(P.S: not = "means not congruent)
4 finally
p is prime (irreductible of Z)
only if: p= x^2 – c*y^2=f1(p) and p not=f2(p)
with f2(p)= x´^2 – c*y´^2 and x not= x´
AND in Z/p x = +- b*y (mod p) AND (+-b)^2=c (mod p)
with c = -1 if p=1 (mod 4)
c = -2 if p=3 (mod 8)
c = +2 if p=7 (mod 8)
I can’t wait for your answers. thank you.
Pingback: Q: Is there a formula for finding primes? Do primes follow a pattern? | Ask a Mathematician / Ask a Physicist