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???
 A: 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 &= 1 \\
    4\cdot 1^2 + 1 &= 5 \\
    4\cdot 2^2 + 1 &= 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 &\not \mid (4s^2 + 1) - (4(s-3)^2 + 1) \\
    3 &\not \mid 4(s^2 - (s-3)^2)\\
    3 &\not \mid 4(6s - 9)\\
\end{align}
But clearly $3 \mid 4(6s - 9)$. So by contradiction, $T$ is the empty set.
A: If
$n=0,1,2,3,4,5$,
$4n^2+1
=1, 5, 17, 37, 65, 101
$,
and all of these
are relatively prime to 24.
If
$n = 6m+k$
where
$0 \le k \le 5 $,
then
$\begin{array}\\
4n^2+1
&=4(6m+k)^2+1\\
&=4(36m^2+12mk+k^2)+1\\
&=4(36m^2+12mk)+4k^2+1\\
&=48(3m^2+mk)+4k^2+1\\
\end{array}
$
so
if $d$ divides both
$4n^2+1$ and $24$,
it also divides
$4k^2+1$.
Since
$24$ and
$2k^2+1$are relatively prime
for
$0 \le k \le 5$,
the only integer
that divides both
$24$ and $4k^2+1$
is $1$.
A: 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!
