2026-10-20 12:13 UTC
@ohad@mathstodon.xyz unfortunately that is not the case. First of all, the proof of termination of Euclid’s algorithm itself is sketchy for this reason, but that is understandable.
Elsewhere, Marcelo argues in the lecture notes that some proofs are best done using the universal property, and others are best done by looking at the algorithm. I agree with that, but unfortunately they won’t have the tools needed to “look at the algorithm” with any rigor for about eight or nine more lectures. So there’s at least a few proofs elsewhere that inspect gcd reduction traces without any mathematical basis for doing so except intuition.
Replies (1)
-
@jonmsterling@mathstodon.xyz 2026-10-20 12:15
@ohad@mathstodon.xyz I think it is good that Marcelo shows both things that are nice to see from a mathematical point of view and things that are nice to see from an algorithmic point of view. But I think it would be important that if the latter arguments are going to be only intuitive and not rigorous (at least, not founded on what we have taught so far), then they should be presented as alternative intuitions to proofs that we already can do in a rigorous way. I would like to set things up so that we can do both kinds of proof rigorously very early on, but this is more surgery than I can accomplish in a few weeks.