# Complete Residue Systems Problem

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

#### Bruno J.

MHF Hall of Honor
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!

#### 1337h4x

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?

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

• 1337h4x

#### 1337h4x

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?

#### Bruno J.

MHF Hall of Honor
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$$.

• BBAmp

Thanks !