Page 1 of 2 12 LastLast
Results 1 to 15 of 20

Math Help - Help Preparing for Final Exam

  1. #1
    Member diddledabble's Avatar
    Joined
    Jul 2009
    Posts
    80

    Post Help Preparing for Final Exam

    I am trying to prepare for my final exam in NT. Any help would be appreciated. These questions are just for study purposes, I messed them up on my homework, etc.

    Reduced Residue System Proof
    Show that if a=b(mod n) then (a,n)= (b,n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by diddledabble View Post
    I am trying to prepare for my final exam in NT. Any help would be appreciated. These questions are just for study purposes, I messed them up on my homework, etc.

    Reduced Residue System Proof
    Show that if a=b(mod n) then (a,n)= (b,n)
    a \equiv b (mod n) \Leftrightarrow n|(b-a) \Rightarrow nk=b-a for some integer k

    Now we show the set of divisors of a and n are the same as the set of divisors of b and n.

    Let d divide a and n.

    nk=b-a \Rightarrow b=nk+a then d divides the RHS so it divides b as well.


    Let d divide b and n.

    nk=b-a \Rightarrow b-nk=a then d divides the LHS so it divides a as well.

    Thus the set of divisors is the same, so their greatest element is the same. so (a,n)=(b,n)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2009
    Posts
    36
    First of all, assuming that a\equiv b \ (mod \ m) we have that if d|m and d|a then d|b.

    Proof:

    a-b=m.k

    m=d.u and a=d.s

    then

    b=d(s-u)

    Now, let d=(a,m) and e=(b,m). Then d|m, d|a so d|b. Hence d|e.
    Similarly, e|m, e|b so e|a. Hence e|d. Therefore d=e
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member diddledabble's Avatar
    Joined
    Jul 2009
    Posts
    80

    Post Another Proof

    Show that if 2n+1 is prime, then n must be a power of 2.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    Not true

    Quote Originally Posted by diddledabble View Post
    Show that if 2n+1 is prime, then n must be a power of 2.
    2\cdot 3 + 1=7 is prime and 3 is not a power of 2.
    Last edited by Gamma; August 4th 2009 at 12:01 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Maybe what you meant was 2^n+1 being prime implies n=2^i for i\in \{0,1,2,...\}. If so, I would check out this:Fermat number - Wikipedia, the free encyclopedia

    For completeness, it should state the n could also be 0.
    Last edited by Gamma; August 4th 2009 at 12:10 PM. Reason: added last bit
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member diddledabble's Avatar
    Joined
    Jul 2009
    Posts
    80
    Quote Originally Posted by Gamma View Post
    2\cdot 3 + 1=7 is prime and 3 is not a power of 2.
    Maybe I messed it up. It is supposed to be proveable. I thought of the counterwxample issue too. Maybe it should be 2^n+1
    or 2^{n+1}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by diddledabble View Post
    Maybe I messed it up. It is supposed to be proveable. I thought of the counterwxample issue too. Maybe it should be 2^n+1
    or 2^{n+1}
    You can't prove something is true if there is a counter-example... that is the beauty of math.

    2|2^{n+1} so it can never be prime if n is a natural number (not including 0), so that would be a pretty dull question. Probably it is what I suggested above.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    May 2009
    Posts
    36
    Gamma,

    Show that IF 2n+1 is prime, then n must be a power of 2.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member diddledabble's Avatar
    Joined
    Jul 2009
    Posts
    80
    Streethot, Everytime I read it I think of a different way to go with it. I think you have it though. 2^n+1 must be a prime to start with.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by streethot View Post
    Gamma,

    Show that IF 2n+1 is prime, then n must be a power of 2.

    Yes, if 7=2\cdot 3 + 1 is prime... which it is for n=3, then 3 should be a power of 2. It is not, therefore this statement is not even close to being true.


    need another let n=5

    how about n=9?



    or n=11?

    need any more?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member diddledabble's Avatar
    Joined
    Jul 2009
    Posts
    80
    But if it should have been 2^n+1 let n=2 that is not a square. I just don;t get this one and fermat seems way to tough to be on the exam.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    May 2009
    Posts
    36
    Sorry, i thought the question was about 2^{m}+1 with m=2^n \ \ n\in\mathbb{N}
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    The statement should be


    IF 2^n+1 is prime, then n is a power of 2 or n=0.

    the proof is given here Fermat number - Wikipedia, the free encyclopedia

    There is nothing complicated about the proof supplied in the link. It is a proven fact, this has to be what the teacher was going for, the other possibilities are either not true or would never be asked on an exam by someone with a PhD in math.

    I am not following what your problem is with this, it is a very straightforward if then statement. The proof goes by contradiction in supposing that n is not a power of two, then it has an odd prime factor. Then you show how you factor 2^n+1 which makes it NOT prime, a contradiction.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by streethot View Post
    Sorry, i thought the question was about 2^{m}+1 with m=2^n \ \ n\in\mathbb{N}
    It is, that is what it means to be a power of 2.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Final Exam Help:/ ?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 25th 2010, 05:17 PM
  2. Final exam tomorrow, need help!
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 4th 2010, 06:11 PM
  3. Final Exam Review - Help
    Posted in the Algebra Forum
    Replies: 5
    Last Post: May 10th 2009, 08:45 PM
  4. final exam help >.<
    Posted in the Math Topics Forum
    Replies: 6
    Last Post: May 3rd 2007, 03:15 PM
  5. Important Questions (Preparing For Final) Need Help
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: May 14th 2006, 05:29 AM

Search Tags


/mathhelpforum @mathhelpforum