Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$ Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$
Let $d=\gcd(4n^2+1,24)$ then we have:
$$d|24n^2+6,24n^2\ \Rightarrow\ d|6\ \Rightarrow\ d|6n^2,4n^2+1\ \Rightarrow\ d|12n^2,12n^2+3\ \Rightarrow\ d|3\ \Rightarrow\ d=1\ or\ 3$$
Using modular equivalence it's very easy to show that $d$ can't be 3,but how can I show it WITHOUT using  modular equivalence???
Theorem. $4n^2 + 1$ is not a multiple of $3$.

Proof. Since $n^2 = (-n)^2$, we need only prove this for
$n \in \mathbb W = \{0, 1, 2, \dots\}$.

Let $T = \{k\in \mathbb W : 3 | 4k^2 + 1\}$.

We need to show that $T$ is the empty set.

If we assume that $T$ is not the empty set, then it must contain a smallest member, say $s$. (This is called "The Well-Ordering Principle".) Then $s$ is the smallest member of $\mathbb W$ such that $3 \mid 4s^2 + 1$.

Note that
\begin{align}
    4\cdot 0^2 + 1 &amp;= 1 \\
    4\cdot 1^2 + 1 &amp;= 5 \\
    4\cdot 2^2 + 1 &amp;= 17 \\
\end{align}
So $s-3 \in \mathbb W$ and $s-3 \not \in T$. But if $3 \mid 4s^2 + 1$ and 
$3 \not \mid 4(s-3)^2 + 1$, then

\begin{align}
    3 &amp;\not \mid (4s^2 + 1) - (4(s-3)^2 + 1) \\
    3 &amp;\not \mid 4(s^2 - (s-3)^2)\\
    3 &amp;\not \mid 4(6s - 9)\\
\end{align}

But clearly $3 \mid 4(6s - 9)$. So by contradiction, $T$ is the empty set.
Finally I could find a desired solution:
We consider 3 cases for $n:n=3k,3k+1,3k+2$
$n^2=9k^2,9k^2+6k+1,9k^2+12k+4\ \Rightarrow\ 4n^2+1=3k'+1,3k'+2,3k'+2$
So $4n^2+1$ is never divisible by 3,thus $d=1$,that's it!