I came across a proof of Euclid's Lemma from https://www.sci.brooklyn.cuny.edu/~mate/misc/euclids_lemma.pdf that used another lemma to assist in the proof:
Let a and c be positive integers and let t be the smallest positive integer such that c | at. Let b be a positive integer such that c | ab. Then t | b. In particular, t | c.
Their proof goes as follows:
Assume t ∤ b; let q and r be such that b = tq + r and 1 ≤ r < t. Then ab = atq + ar. As c is a divisor of the left-hand side and of the first term on the right-hand side, it follows that c is also a divisor of the second term on the right-hand side; i.e., c | ar. This, however, contradicts the minimality of t. This contraction shows that t | b. Since we have c | ac, this assertion with c = b shows that t | c holds.
I understand why t|b by contradiction. What I don't understand is how they assert c|ac, and that c=b, and how that leads to being able to assert that t|c. Does anyone have any insight into their logic that I'm missing?
You understand that if $\color{green}t$ is the smallest positive integer such that $\color{blue}{c} \mid a\color{green}t$, and $\color{red}b$ is any integer such that $\color{blue}{c} \mid a\color{red}b$, then $\color{green}t \mid \color{red}b$.
Using this lemma, since $\color{blue}{c} \mid a\color{green}t$ ($\color{green}t$ is the smallest such positive integer) and $\color{blue}c \mid a\color{red}c$, we have $$\color{green}t \mid \color{red}c$$
Note the distinction in the red and blue colours.