I have a similar type of problem on an assignment, but with

instead. However, I'm not allowed to use modular arithmetic. Using the

example, I was just wondering if I could restate this last part as:

By the Fundamental Theorem of Arithmetic, there must be a prime of form

such that

. But

is not divisible by any prime of form

by our assumption. This is a contradiction, thus, there must exist infinitely many primes of the form

.

Such a proof should also hold for the case of primes in the form of

too right?