[number theory] let p be the smallest prime divisor of n, prove that gcd(n, p-1)=1
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
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.
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!