# Complete Residue Systems Problem

• May 21st 2010, 04:46 PM
1337h4x
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!
• May 21st 2010, 04:54 PM
Bruno J.
Quote:

Originally Posted by 1337h4x
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 $\displaystyle 2^n+1$ can be prime only if $\displaystyle n$ is a power of $\displaystyle 2$, while a number of the form $\displaystyle 2^n-1$ can be prime only if $\displaystyle n$ is prime. Thus $\displaystyle n$ must be both prime and a power of $\displaystyle 2$, i.e. $\displaystyle n=2$.

2. Suppose two of them are congruent modulo $\displaystyle m$... you'll reach a contradiction!
• May 21st 2010, 05:03 PM
1337h4x
Quote:

Originally Posted by Bruno J.
1. No. A number of the form $\displaystyle 2^n+1$ can be prime only if $\displaystyle n$ is a power of $\displaystyle 2$, while a number of the form $\displaystyle 2^n-1$ can be prime only if $\displaystyle n$ is prime. Thus $\displaystyle n$ must be both prime and a power of $\displaystyle 2$, i.e. $\displaystyle n=2$.

2. Suppose two of them are congruent modulo $\displaystyle 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?
• May 22nd 2010, 02:58 PM
BBAmp
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: $\displaystyle 3n \equiv 4n(modm)$. If you cancel you get $\displaystyle 3 \equiv 4(modm)$. Then if you work it out algebraically $\displaystyle -1=km$ for some integer k. Well it was stated that $\displaystyle 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.
• May 22nd 2010, 04:09 PM
1337h4x
Quote:

Originally Posted by BBAmp
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: $\displaystyle 3n \equiv 4n(modm)$. If you cancel you get $\displaystyle 3 \equiv 4(modm)$. Then if you work it out algebraically $\displaystyle -1=km$ for some integer k. Well it was stated that $\displaystyle 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?
• May 22nd 2010, 04:23 PM
Bruno J.
Quote:

Originally Posted by 1337h4x
Can anyone else confirm his results?

Yes, it's essentially what must be done. If $\displaystyle j n \equiv k n \mod m$ then $\displaystyle j \equiv k \mod m$ (here we use that $\displaystyle (m,n)=1$). But $\displaystyle j,k$ are elements of the complete residue system $\displaystyle \{0,1,\dots,m-1\}$, which implies $\displaystyle j=k$.
• May 22nd 2010, 04:25 PM
1337h4x
Thanks !