Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Ah, thanks AVS! I wasn't expecting that performing the algorithm exactly as I wrote it would give a speed-up, but I was thinking that one of the other speed-ups might improve the algorithm I wrote to be comparable to others. One knows that the first remainder less than p will occur almost exactly half-way through the Euclidean algorithm with $p^2$ and $ap+1$, so jumping to the middle step will put you very close.
Thank you François. I can only report that I got the gist of your entire response, but I take from it that you believe it possible that the infinitude of primes is necessary in the proof and have a potential explanation for this. If this is indeed the case, then I would find it fascinating. This has been bugging me the way needing analysis to prove the fundamental theorem of algebra bugs some people, but at least there, I understand why getting your hands on $\mathbb{C}$ without analysis is difficult.
@Felipe: Good point, and if you find me a direct proof from Euler's product that the infinitude of primes implies the transcendence of the left side, then such an argument would surely force me to believe that the transcendence of pi and the infinitude of primes are inextricably entwined.
@Vladimir and Felipe: We all lump algebraic/transcendental numbers under the number theory umbrella, but I do not accept that every pair of results under that umbrella must be seen as entwined. Example from algebra: Elliptic curves are related to the j-function, which are related to the monster group. If I said I was shocked that there was a connection between elliptic curves and the monster group, someone could say that they both fall under "algebra". I do not believe your comments are quite this extreme, but I still don't believe that saying "both are number theory" is a strong point.
Thank you. I'll check out Niven's proof. Do you know if he uses the infinitude of primes? I'm guessing his proof is similar to that in his Monthly article, in which case he does.
@Joel: Of course students who can handle Galois theory can handle Euclid's proof, and many of them have already seen it. It bothers me for aesthetic reasons, not practical ones. @Leonid: Thank you, but transcendence is definitely required for my class.
@Qiaochu: True, and perhaps I haven't thought enough about the proofs I have been looking at (for instance, the one by Niven, Monthly, 46, no. 8), but it doesn't seem to me that the introduction of the prime p in the proof is used directly to make this distinction (but perhaps indirectly, that is what is accomplished). The main distinction does not seem to be between the integral and non-integral, but rather between integers divisible by p and not.
