Complete Residue Systems Problem

Apr 2009
96
0
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
Jun 2009
1,266
498
Canada
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!
 
Apr 2009
96
0
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 2010
17
2
Cleveland,OH/Madison,WI/Queens,NY
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.
 
  • Like
Reactions: 1337h4x
Apr 2009
96
0
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
Jun 2009
1,266
498
Canada
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\).
 
  • Like
Reactions: BBAmp