# Thread: Complete Residue Systems Problem

1. ## 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!

2. 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!

3. 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?

4. 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.

5. 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?

6. 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$.

7. Thanks !