Results 1 to 7 of 7

Math Help - Complete Residue Systems Problem

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Complete Residue Systems Problem

    Hello everyone, I have a question on complete residue systems that I do not understand.

    1. Are there any twin primes (like 11 and 13, or 3 and 5) of the form (2^n)-1, (2^n) +1, for n > 2?

    If there are, do you have an example? If not, could you explain why there aren't any?

    2. Assume that m and n are integers where GCD[m,n]=1. Assume m and n are > 1. The set S={0*n,1*n,2*n,...,(m-1)*n} is a complete residue system modulo m. How can I prove this ?

    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by 1337h4x View Post
    Hello everyone, I have a question on complete residue systems that I do not understand.

    1. Are there any twin primes (like 11 and 13, or 3 and 5) of the form (2^n)-1, (2^n) +1, for n > 2?

    If there are, do you have an example? If not, could you explain why there aren't any?

    2. Assume that m and n are integers where GCD[m,n]=1. Assume m and n are > 1. The set S={0*n,1*n,2*n,...,(m-1)*n} is a complete residue system modulo m. How can I prove this ?

    Any help is appreciated!
    1. No. A number of the form 2^n+1 can be prime only if n is a power of 2, while a number of the form 2^n-1 can be prime only if n is prime. Thus n must be both prime and a power of 2, i.e. n=2.

    2. Suppose two of them are congruent modulo m... you'll reach a contradiction!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by Bruno J. View Post
    1. No. A number of the form 2^n+1 can be prime only if n is a power of 2, while a number of the form 2^n-1 can be prime only if n is prime. Thus n must be both prime and a power of 2, i.e. n=2.

    2. Suppose two of them are congruent modulo m... you'll reach a contradiction!
    So in your first point, you mean if n = 2, 4, 8, 16, etc?

    Second point: How does that even work?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie BBAmp's Avatar
    Joined
    May 2010
    From
    Cleveland,OH/Madison,WI/Queens,NY
    Posts
    17
    Point 1:
    Bruno had a very good answer but I don't think you understand so let me clarify:

    To have a number n fit your equation you will need an integer that is both prime and a power of two. The only number that fits this requirement is 2 since 2 is both a prime and a power of two. Any other power of two will not work since they are not prime. Thus there are no twin primes that fit your equation.

    For point 2.. I don't fully understand the problem either because I am new to number theory but I will give it a shot and I will gladly take criticism from anyone who understands the problem so I know what I am doing wrong. I will go by what Bruno suggests and work till I find a contradiction. Suppose you have two integers out of the set. Lets use for instance 3n and 4n and set them congruent to each other with some modulo m: 3n \equiv 4n(modm) . If you cancel you get 3 \equiv 4(modm). Then if you work it out algebraically  -1=km for some integer k. Well it was stated that m > 1 and the only way for that to happen is for k to be a non-integer. We have reached a contradiction and disproved the problem. Can anyone comment on my methodology?

    BTW latex in a math forum = freakin awesome.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by BBAmp View Post
    Point 1:
    Bruno had a very good answer but I don't think you understand so let me clarify:

    To have a number n fit your equation you will need an integer that is both prime and a power of two. The only number that fits this requirement is 2 since 2 is both a prime and a power of two. Any other power of two will not work since they are not prime. Thus there are no twin primes that fit your equation.

    For point 2.. I don't fully understand the problem either because I am new to number theory but I will give it a shot and I will gladly take criticism from anyone who understands the problem so I know what I am doing wrong. I will go by what Bruno suggests and work till I find a contradiction. Suppose you have two integers out of the set. Lets use for instance 3n and 4n and set them congruent to each other with some modulo m: 3n \equiv 4n(modm) . If you cancel you get 3 \equiv 4(modm). Then if you work it out algebraically  -1=km for some integer k. Well it was stated that m > 1 and the only way for that to happen is for k to be a non-integer. We have reached a contradiction and disproved the problem. Can anyone comment on my methodology?

    BTW latex in a math forum = freakin awesome.
    Can anyone else confirm his results?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by 1337h4x View Post
    Can anyone else confirm his results?
    Yes, it's essentially what must be done. If j n \equiv k n \mod m then j \equiv k \mod m (here we use that (m,n)=1). But j,k are elements of the complete residue system \{0,1,\dots,m-1\}, which implies j=k.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Apr 2009
    Posts
    96
    Thanks !
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Residue problem
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: April 14th 2010, 09:50 PM
  2. Proof with reduced residue systems
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: November 11th 2009, 12:33 PM
  3. quadratic residue problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 2nd 2009, 03:43 AM
  4. complete residue modulo
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 5th 2009, 02:53 PM
  5. residue problem
    Posted in the Calculus Forum
    Replies: 5
    Last Post: April 22nd 2008, 11:09 AM

Search Tags


/mathhelpforum @mathhelpforum