[number theory] let p be the smallest prime divisor of n, prove that gcd(n, p-1)=1

SOLVED!

let p be the smallest prime divisor of n, prove that gcd(n, p-1)=1.
already got the proof for an even n, but im stuck when n is odd.

Posted Nov 5, 2018, 4:41 AM UTC

13
LassT•

Assume gcd(n,p-1)=k for k>1, now you can write k as a product of primes. Each of these primes are less than p and also divide n hence we have found a smaller prime divisor of n, this is a contradiction so k=1.

2
BluDavidOP•

what if k = 3 or 2? it cant be written as a product of smaller primes since 3=3*1, in this cases there would be no contradiction, sorry if im missing something.
edit: you are right, i can now see it, thanks!

1

If gcd(n, p-1) was not 1, then there exists some prime P < p-1 such that P | p-1 and P | n.

But this contradicts the fact that p is the smallest prime divisor of n.

2