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)
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)
$\displaystyle a \equiv b $ (mod n) $\displaystyle \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.
$\displaystyle nk=b-a \Rightarrow b=nk+a$ then d divides the RHS so it divides b as well.
Let d divide b and n.
$\displaystyle 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)
First of all, assuming that $\displaystyle a\equiv b \ (mod \ m)$ we have that if $\displaystyle d|m$ and $\displaystyle d|a$ then $\displaystyle d|b$.
Proof:
$\displaystyle a-b=m.k$
$\displaystyle m=d.u$ and $\displaystyle a=d.s$
then
$\displaystyle b=d(s-u)$
Now, let $\displaystyle d=(a,m)$ and $\displaystyle e=(b,m)$. Then $\displaystyle d|m$, $\displaystyle d|a$ so $\displaystyle d|b$. Hence $\displaystyle d|e$.
Similarly, $\displaystyle e|m$, $\displaystyle e|b$ so $\displaystyle e|a$. Hence $\displaystyle e|d$. Therefore $\displaystyle d=e$
Maybe what you meant was $\displaystyle 2^n+1$ being prime implies $\displaystyle n=2^i$ for $\displaystyle 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.
You can't prove something is true if there is a counter-example... that is the beauty of math.
$\displaystyle 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.
The statement should be
IF $\displaystyle 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 $\displaystyle 2^n+1$ which makes it NOT prime, a contradiction.