Results 1 to 4 of 4

Thread: Modular arithmetic HELP!!

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    40

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by qtpipi View Post
    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
    $\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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, qtpipi!

    Another approach . . .


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

    Prove that $\displaystyle n^2 + 2$ is composite.
    Since $\displaystyle n \equiv 5\text{ (mod 6)}$, then $\displaystyle n \:=\:5 + 6k$ for some integer $\displaystyle k.$


    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.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Soroban View Post
    $\displaystyle \text{Hence: }\;A \;=\;\underbrace{3(12k^2 + 20k + 9)}_{\text{a multiple of 3}}$


    Therefore, $\displaystyle A$ is composite.
    Hi Soroban.

    It might be worth mentioning also that $\displaystyle 12k^2 + 20k + 9\ne1$ for all $\displaystyle k\ge0.$ It’s clear in this particular problem, but this is something which people tend to neglect when doing this sort of problems.
    Last edited by TheAbstractionist; May 16th 2009 at 01:30 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 28th 2010, 05:08 AM
  2. Arithmetic Modular help!!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 24th 2010, 08:44 AM
  3. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 2nd 2009, 12:17 PM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 13th 2008, 03:17 PM
  5. Modular arithmetic help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 4th 2008, 08:47 AM

Search Tags


/mathhelpforum @mathhelpforum