n e N, and n = 5 (mod6). prove that n^2 + 2 is composite. Can someone give me a detailed, step by step proof of how to do this?? I'm completely confused when it comes to modular arithmetic

Printable View

- May 12th 2009, 09:20 PMqtpipiModular arithmetic HELP!!
n e N, and n = 5 (mod6). prove that n^2 + 2 is composite. Can someone give me a detailed, step by step proof of how to do this?? I'm completely confused when it comes to modular arithmetic

- May 13th 2009, 01:24 AMMoo
Hello,

$\displaystyle n\equiv 5(\bmod 6) \Rightarrow n^2 \equiv 5^2 (\bmod 6)\Rightarrow n^2 \equiv 1(\bmod 6)$

Hence $\displaystyle n^2+2\equiv 3(\bmod 6)$

So $\displaystyle \exists k\in\mathbb{N} ~:~ n^2+2=3+6k$

It should be obvious that 3 divides $\displaystyle n^2+2$. And since $\displaystyle n\equiv 5(\bmod 6)$, it follows that $\displaystyle n\geq 5$, and hence $\displaystyle n^2+2> 3$.

Therefore, $\displaystyle n^2+2$ is composite. - May 13th 2009, 05:19 AMSoroban
Hello, qtpipi!

Another approach . . .

Quote:

$\displaystyle n \in N\text{, and }n \equiv 5\text{ (mod 6)}$

Prove that $\displaystyle n^2 + 2$ is composite.

Let $\displaystyle A \:=\:n^2+2$

. . Then: .$\displaystyle A \:=\: (5+6k)^2 + 2 \;=\;25 + 60k + 36k^2 + 2 \;=\;36k^2 + 60x + 27$

$\displaystyle \text{Hence: }\;A \;=\;\underbrace{3(12k^2 + 20x + 9)}_{\text{a multiple of 3}}$

Therefore, $\displaystyle A$ is composite.

- May 16th 2009, 12:02 PMTheAbstractionist