Thread: Help Preparing for Final Exam

I am trying to prepare for my final exam in NT. Any help would be appreciated. These questions are just for study purposes, I messed them up on my homework, etc.

Reduced Residue System Proof
Show that if a=b(mod n) then (a,n)= (b,n)

Originally Posted by diddledabble

I am trying to prepare for my final exam in NT. Any help would be appreciated. These questions are just for study purposes, I messed them up on my homework, etc.

Reduced Residue System Proof
Show that if a=b(mod n) then (a,n)= (b,n)

(mod n) for some integer k

Now we show the set of divisors of a and n are the same as the set of divisors of b and n.

Let d divide a and n.

then d divides the RHS so it divides b as well.


Let d divide b and n.

then d divides the LHS so it divides a as well.

Thus the set of divisors is the same, so their greatest element is the same. so (a,n)=(b,n)

First of all, assuming that we have that if and then .

Proof:



and

then



Now, let and . Then , so . Hence .
Similarly, , so . Hence . Therefore

Show that if 2n+1 is prime, then n must be a power of 2.

Originally Posted by diddledabble

Show that if 2n+1 is prime, then n must be a power of 2.

is prime and 3 is not a power of 2.

Maybe what you meant was being prime implies for . If so, I would check out this:Fermat number - Wikipedia, the free encyclopedia

For completeness, it should state the n could also be 0.

Originally Posted by Gamma

is prime and 3 is not a power of 2.

Maybe I messed it up. It is supposed to be proveable. I thought of the counterwxample issue too. Maybe it should be
or

Originally Posted by diddledabble

Maybe I messed it up. It is supposed to be proveable. I thought of the counterwxample issue too. Maybe it should be
or

You can't prove something is true if there is a counter-example... that is the beauty of math.

so it can never be prime if n is a natural number (not including 0), so that would be a pretty dull question. Probably it is what I suggested above.

Gamma,

Show that IF 2n+1 is prime, then n must be a power of 2.

Streethot, Everytime I read it I think of a different way to go with it. I think you have it though. 2^n+1 must be a prime to start with.

Originally Posted by streethot

Gamma,

Show that IF 2n+1 is prime, then n must be a power of 2.

Yes, if is prime... which it is for n=3, then 3 should be a power of 2. It is not, therefore this statement is not even close to being true.


need another let n=5

how about n=9?



or n=11?

need any more?

But if it should have been let n=2 that is not a square. I just don;t get this one and fermat seems way to tough to be on the exam.

Sorry, i thought the question was about with

The statement should be


IF is prime, then n is a power of 2 or n=0.

the proof is given here Fermat number - Wikipedia, the free encyclopedia

There is nothing complicated about the proof supplied in the link. It is a proven fact, this has to be what the teacher was going for, the other possibilities are either not true or would never be asked on an exam by someone with a PhD in math.

I am not following what your problem is with this, it is a very straightforward if then statement. The proof goes by contradiction in supposing that n is not a power of two, then it has an odd prime factor. Then you show how you factor which makes it NOT prime, a contradiction.

Originally Posted by streethot

Sorry, i thought the question was about with

It is, that is what it means to be a power of 2.