Modular arithmetic HELP!!

**qtpipi** · May 12th 2009, 09:20 PM

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

**Moo** · May 13th 2009, 01:24 AM

Hello,

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.

**Soroban** · May 13th 2009, 05:19 AM

Hello, qtpipi!

Another approach . . .

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

**TheAbstractionist** · May 16th 2009, 12:02 PM

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.

Thread: Modular arithmetic HELP!!

LinkBack

Thread Tools

Display

Modular arithmetic HELP!!

Similar Math Help Forum Discussions

Modular Arithmetic

Arithmetic Modular help!!

modular arithmetic

Modular arithmetic

Modular arithmetic help

Search Tags