Let $a$ and $n$ be natural numbers with $(a,n) = 1$. Then $(a^j,n) = 1$ for any natural number $j$. I am aware that the proofs on this site use induction, the binomial theorem, or that relatively prime numbers can be written as $ax + by = 1$. However, I "proved" this myself without these since I didn't see why I really needed to use them. It seems like the most obvious way to prove it and so I guess there must be a good reason why the answers on here didn't use it.
If $(a,n) = 1$ then $a = p^{r_1}_1 \cdot \cdot \cdot p^{r_k}_k$ where each $p$ is prime. We have that $a^j = p^{jr_1}_1 \cdot \cdot \cdot p^{jr_k}_k$ which is clearly a product of the same primes of $a$ with the only difference being that each prime is raised to the $jth$ power. Hence $(a^j,n) = 1$.
My answer is a little bit of a frame challenge. Based on the title of the question and some of the comments posted below the question, it seems that the correct question is something like:
In addition to this question (which seems to be hinted at in the title, there also seems to be a secondary question, which is
The second question is easier to answer: your proof is fundamentally (heh heh) correct, if a little imprecise. Other commenters have pointed out how you could improve precision, and I suspect that one of them may provide an answer, so I am going to ignore this question. To me, the first question is more interesting, anyway.
To answer this first question, we need to agree on what is meant by an "elementary" proof. By an elementary proof, I mean a proof which depends on the smallest number of theorems (where both "smallest number" and "theorem" are somewhat nebulously defined). Elementary proofs are often actually quite a bit harder than more "advanced" proofs, because you have to get your hands dirty and actually work the details out—the goal is to avoid invoking theorems so that you can actually see how the argument proceeds. This can make things harder, as the proof may become more convoluted. Analyzing proofs of Theorem 1, I see the following:
A standard proof
The proof of Theorem 1 with which I am most familiar is by induction and uses some moderately powerful theorems for the base case. The proof of the base case is roughly the proof given on proofwiki, which depends on something like Bezout's theorem somewhere down the line. I would argue that this proof is relatively elementary: it depends chiefly on the Principle of Mathematical Induction (which is a big theorem), and either a tedious elementary argument or an application of Bezout (or something similar). Let's call this two big theorems.
Proof via the FTA
On the other hand, your proof is a relatively direct application of the Fundamental Theorem of Arithmetic (FTA). The FTA has two pieces: an existence bit, and a uniqueness bit. The existence bit is usually proved via the Principle of Mathematical Induction or via the Well Ordering Principle (which is equivalent to the Principle of Mathematical Induction)—both of our proofs require this particular "big theorem".
The uniqueness bit can be proved in a number of ways: Wikipedia offers two proofs, one of which is elementary (-ish... it also seems to depend on the Well Ordering Principle), and the other of which relies on Euclid's lemma, which in turn is typically proved with Bezout's Lemma. proofwiki gives another proof, which relies on something it calls the Fundamental Theorem of Equivalence relations, which seems like a "big theorem" to me (it is called "fundamental", after all, and the proof requires some work). In any event, proving the FTA seems to require at least two "big theorems", if not more, and then you have to actually invoke the FTA to prove Theorem 1.
Conclusion
By this analysis, I would argue that one "needs" induction to prove Theorem 1 (either directly, or in the proof of the FTA, or in the proof of the FTA via the Well-Ordering Principle). Bezout's lemma is likely unnecessary, though it seems that some weakened form of Bezout is probably required. Invoking the FTA doesn't seem to get around this, but does sweep it under the rug a bit.