Thread: Number theory

(i) Let p the smallest prime divisor of n. Show that there exist integers a, b, such that an+b(p-1)=1

(ii) For every n>1 show that n does not divide (2^n)-1

Please ANY help?

Originally Posted by AlexHall

(i) Let p the smallest prime divisor of n. Show that there exist integers a, b, such that an+b(p-1)=1

Hint: n and p-1 must be co-prime (because any common factor would have to be less than p, and therefore could not divide n).

Originally Posted by AlexHall

(ii) For every n>1 show that n does not divide (2^n)-1

(I was totally unable to see how to do this until I realised that you need to use part (i).)

Suppose that n does divide $\displaystyle 2^n-1$. Let p be the smallest prime divisor of n, then p must divide $\displaystyle 2^n-1$. In other words, $\displaystyle 2^n\equiv1\!\!\pmod p$. Since p is prime, it follows from Fermat's Little Theorem that $\displaystyle 2^{p-1}\equiv1\!\!\pmod p$. Then by part (i), $\displaystyle 2 = 2^{an+b(p-1)}= (2^n)^a(2^{p-1})^b\equiv1\!\!\pmod p$, contradiction!

Edit. I forgot to say that that proof doesn't work if p=2 (because 2 and p are not then co-prime, so Fermat's theorem goes wrong!). But the result is obvious when p=2, because n would then be even, and (2^n)-1 is odd.

Thank you so much.