# Help Preparing for Final Exam

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jul 27th 2009, 11:06 AM
diddledabble
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)
• Jul 27th 2009, 03:54 PM
Gamma
Quote:

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)

$a \equiv b$ (mod n) $\Leftrightarrow n|(b-a) \Rightarrow nk=b-a$ 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.

$nk=b-a \Rightarrow b=nk+a$ then d divides the RHS so it divides b as well.

Let d divide b and n.

$nk=b-a \Rightarrow b-nk=a$ 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)
• Aug 3rd 2009, 10:13 PM
streethot
First of all, assuming that $a\equiv b \ (mod \ m)$ we have that if $d|m$ and $d|a$ then $d|b$.

Proof:

$a-b=m.k$

$m=d.u$ and $a=d.s$

then

$b=d(s-u)$

Now, let $d=(a,m)$ and $e=(b,m)$. Then $d|m$, $d|a$ so $d|b$. Hence $d|e$.
Similarly, $e|m$, $e|b$ so $e|a$. Hence $e|d$. Therefore $d=e$
• Aug 4th 2009, 11:55 AM
diddledabble
Another Proof
Show that if 2n+1 is prime, then n must be a power of 2.
• Aug 4th 2009, 12:01 PM
Gamma
Not true
Quote:

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

$2\cdot 3 + 1=7$ is prime and 3 is not a power of 2.
• Aug 4th 2009, 12:08 PM
Gamma
Maybe what you meant was $2^n+1$ being prime implies $n=2^i$ for $i\in \{0,1,2,...\}$. If so, I would check out this:Fermat number - Wikipedia, the free encyclopedia

For completeness, it should state the n could also be 0.
• Aug 4th 2009, 12:09 PM
diddledabble
Quote:

Originally Posted by Gamma
$2\cdot 3 + 1=7$ 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 $2^n+1$
or $2^{n+1}$
• Aug 4th 2009, 12:12 PM
Gamma
Quote:

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 $2^n+1$
or $2^{n+1}$

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

$2|2^{n+1}$ 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.
• Aug 4th 2009, 12:13 PM
streethot
Gamma,

Show that IF 2n+1 is prime, then n must be a power of 2.
• Aug 4th 2009, 12:16 PM
diddledabble
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.
• Aug 4th 2009, 12:17 PM
Gamma
Quote:

Originally Posted by streethot
Gamma,

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

Yes, if $7=2\cdot 3 + 1$ 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

or n=11?

need any more?
• Aug 4th 2009, 12:23 PM
diddledabble
But if it should have been $2^n+1$ 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.
• Aug 4th 2009, 12:30 PM
streethot
Sorry, i thought the question was about $2^{m}+1$ with $m=2^n \ \ n\in\mathbb{N}$
• Aug 4th 2009, 12:33 PM
Gamma
The statement should be

IF $2^n+1$ 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 $2^n+1$ which makes it NOT prime, a contradiction.
• Aug 4th 2009, 12:35 PM
Gamma
Quote:

Originally Posted by streethot
Sorry, i thought the question was about $2^{m}+1$ with $m=2^n \ \ n\in\mathbb{N}$

It is, that is what it means to be a power of 2.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last