Proving $\mathbb{Z}$ is a PID without appealing to the Euclidean algorithm This is a really vague question, and I'm not even sure how to pose it correctly, but I will do my best.
The Euclidean algorithm works in $\mathbb{Z}$, so $\mathbb{Z}$ is a Euclidean domain; since Euclidean domains are PIDs, it follows that $\mathbb{Z}$ is a PID. I was wondering if there was a way to prove that $\mathbb{Z}$ is a PID that does not appeal to the Euclidean algorithm (i.e. without assuming $\mathbb{Z}$ is a Euclidean domain) or without showing, during the course of the proof, that the algorithm holds (for an element).
Here's an attempt. Let $I$ be a proper ideal of $\mathbb{Z}$, and let $a$ be the smallest positive element in $I$. I claim that $I = (a)$. Let $b \in I$ not be a multiple of $a$. We can assume WLOG that $b > 0$ (and so $b > a$ since $a$ is minimal among positive elements), for otherwise we can apply the following argument to $-b \in I$, which is also not a multiple of $a$. Let $A = \{c > 0 \mid \exists k \in \mathbb{Z}_{\geq 0} : c = b - ka\} \subseteq I$. $A$ is finite and bounded below by $0$, so it has a minimal element $d$. We need to have $d < a$, for otherwise $e = d - a \in A$ would contradict the minimality of $d$. But $d < a$ is a contradiction to the minimality of $a$, and so $b$ has to be a multiple of $a$. Hence $I = (a)$. 
The problem I have with this proof is that, during the course of it, we proved that $b = ka + d$ with $d < a$, which is exactly the Euclidean algorithm except for the case $d = 0$, which I tacitly assumed when forcing $b$ to not be a multiple of $a$ and $A$ to have positive elements - a proper proof would have mentioned those cases and thus showed that $\mathbb{Z}$ is a Euclidean domain. 
First, is there a proof that does not involve this sort of argument? Second, I'm more interested in the following proof theoretic/logical phenomenon. Say $\varphi, \psi$ are two one-variable propositions (doesn't really matter how many variables they have) such that, for all $x$ for which $\varphi(x)$ holds, $\psi(x)$ holds. If $\varphi(y)$ holds (and hence $\psi(y)$ holds), can we prove $\psi(y)$ without appealing to the truth of $\varphi(y)$? I'm going to tag this question as abstract-algebra as well as logic, but let me know if the logic tag is inappropriate. 
 A: I think the following works. I need that there are finitely many classes mod $b$ and Euclid's lemma. The latter can be proved without the algorithm as Euclid did (see second proof here: link), while for the former follows from $\mathbb Z$ being cyclic, and everything mod $b$ having order $b$ or less. 
Proof:
Let's prove something less first: $\mathbb Z$ is a unique factorization domain. This has a standard proof by Euclid's lemma (a prime divides a product iff it divides some factor. This has a proof via the fact that $a/b$ is a reduced fraction iff $a,b$ are relatively prime iff $a,b$ are minimal). 
Now, consider an ideal generated by $(a,b).$ By the above, they have unique factorizations, from which we can read off their greatest common divisor $d.$ 
We will show that for relatively prime (ie, having gcd $1$) $a,b,$ we have $a^m + nb =1,$ and so $(a,b)=\mathbb Z.$ 
First, again by Euclids lemma, note that $a^k$ is relatively prime to $b$ for every $k.$ Further there are finitely many residue classes modulo $b.$ This is because $\mathbb Z^+$ is cyclic and hence it's quotients are too (this is from the observation that $(b) +(b) + \ldots =(b).$ See here: link), plus noting that everything mod $b$ has order at most $b.$ 
So there must be some powers $k< j$ such that $$a^k = a^j + ib$$
This implies
$$a^k (1 - a^{j-k}) = ib$$
But recall $a^k,b$ are relatively prime. So $b$ can't divide $a^k$ and hence must divide $1- a^{j-k}.$ so we have, after rearranging:
$$1= bn + a^{j-k}$$
Which implies that for $a,b$ relatively prime, $1$ is in $(a,b)$ and hence this ideal is $\mathbb Z.$
So by unique factorization and definition of GCD, we can write $$(a,b) = (d)(a/d, b/d)=(d) \mathbb Z =(d)$$ as desired.
