Saturday, 5 November 2016

gcd and lcm - Show that a positive integer ninmathbbN is prime if and only if gcd(n,m)=1 for all $0




Show that a positive integer nN is prime if and only if gcd(n,m)=1 for all $0

I know that I can write n=km+r for some k,rZ since n>m



and also that 1=an+bm. for some a,bZ



Further, I know that n>1 if I'm to show n is prime.



I'm not sure how I would go about showing this in both directions though.


Answer




Hint: If d divides n, then gcd(d,n)=d.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...