I noticed the place Elon Musk posted Grok’s reply to the immediate “What are probably the most lovely theorems.” I appeared on the checklist, and there have been no surprises, as you’d count on from a program that works by predicting the most probably sequence of phrases primarily based on analyzing net pages.
There’s just one theorem on the checklist that hasn’t appeared on this weblog, so far as I can recall, and that’s Fermat’s theorem that an odd prime p will be written because the sum of two squares if and provided that p = 1 mod 4. The “provided that” route is simple [1] however the “if” route takes extra effort to show.
If p is a main and p = 1 mod 4, Fermat’s theorem ensures the existence of x and y such that
Gauss’ system
Stan Wagon [2] gave an algorithm for locating a pair (x, y) to fulfill the equation above [2]. He additionally presents “a good looking system attributable to Gauss” which “doesn’t appear to be of any worth for computation.” Gauss’ system says that if p = 4ok + 1, then an answer is
For x and y we select the residues mod p with |x| and |y| lower than p/2.
Why would Wagon say Gauss’ system is computationally ineffective? The variety of multiplications required is seemingly on the order of p and the scale of the numbers concerned grows like p!.
You may get round the issue of intermediate numbers getting too massive by finishing up all calculations mod p, however I don’t see a means of implementing Gauss’ system with lower than O(p) modular multiplications [3].
Wagon’s algorithm
If we wish to categorical a big prime p as a sum of two squares, an algorithm requiring O(p) multiplications is impractical. Wagon’s algorithm is rather more environment friendly.
You could find the main points of Wagon’s algorithm in [3], however the two key elements are discovering a quadratic non-residue mod p (a quantity c such that c ≠ x² mod p for any x) and the Euclidean algorithm. Since half the numbers between 1 and p − 1 are quadratic non-residues, you’re very prone to discover a non-residue after a number of makes an attempt.
[1] The sq. of an integer is both equal to 0 or 1 mod 4, so the sum of two squares can’t equal 3 mod 4.
[2] Stan Wagon. The Euclidean Algorithm Strikes Once more. The American Mathematical Month-to-month, Vol. 97, No. 2 (Feb., 1990), pp. 125-129.
[3] Wilson’s theorem provides a quick method to compute (n − 1)! mod n. Possibly there’s some analogous id that would pace up the calculation of the required factorials mod p, however I don’t know what it might be.
