So the question is an 'if and only if' statement meaning that it needs to be proved both ways. I have proved the first direction (if $n$ is prime then either $hcf(a,n)=1$ or $a∣n$). However, I am struggling to prove the opposite direction.
Asked
Active
Viewed 947 times
0
-
You can let $a$ run through $2,3,4,\ldots,n-1$. Does any of those $a$ divide your $n$? What can you conclude? (By the way, what is the definition of prime you use?) – Jeppe Stig Nielsen Oct 25 '17 at 19:46
-
@JeppeStigNielsen that the prime's has only divisors, itself and 1. Also, surely some number between 2 and n-1 would divide n as you cannot assume it is prime doing the backwards implication? – User19023 Oct 25 '17 at 19:50
-
You cannot assume $n$ is prime in this direction, but you do need to prove that $n$ is prime. One way of doing the latter would be to check that no non-trivial divisor $a$ exists. Agree? – Jeppe Stig Nielsen Oct 25 '17 at 20:25
-
1hcf = highest common factor , isn't it ? You should mention it as it is not a very classical abbreviation. – Jean Marie Oct 25 '17 at 20:43
-
Likely duplicate: Let $x$ be greater than $1$. Prove $x$ is prime if and only if for every integer $y$, either $\gcd(x,y)=1$ or $x\mid y$. – Jeppe Stig Nielsen Oct 25 '17 at 22:33