Modular arithmetic HELP!!

• May 12th 2009, 09:20 PM
qtpipi
Modular 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 AM
Moo
Hello,
Quote:

Originally Posted by qtpipi
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

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

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

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

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

Therefore, $n^2+2$ is composite.
• May 13th 2009, 05:19 AM
Soroban
Hello, qtpipi!

Another approach . . .

Quote:

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

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

Since $n \equiv 5\text{ (mod 6)}$, then $n \:=\:5 + 6k$ for some integer $k.$

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

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

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

Therefore, $A$ is composite.

• May 16th 2009, 12:02 PM
TheAbstractionist
Quote:

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

Therefore, $A$ is composite.

Hi Soroban.

It might be worth mentioning also that $12k^2 + 20k + 9\ne1$ for all $k\ge0.$ It’s clear in this particular problem, but this is something which people tend to neglect when doing this sort of problems.