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???

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$.
