Results 1 to 4 of 4

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

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,909
    Thanks
    769
    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.

    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
    \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.
    Last edited by TheAbstractionist; May 16th 2009 at 02: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: March 28th 2010, 06:08 AM
  2. Arithmetic Modular help!!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 24th 2010, 09:44 AM
  3. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2009, 01:17 PM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 04:17 PM
  5. Modular arithmetic help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2008, 09:47 AM

Search Tags


/mathhelpforum @mathhelpforum