Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$

Question

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

Answer 1

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!

Answer 2

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.

Answer 3

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