Is a prime number $P$ always co-prime with $n$ if $1 < n < P$?

77 Views Asked by At

Is a prime number $P$ always co-prime with n such that $$1 < n < P?$$ This would also make sense to me because, just to establish firm definitions, two numbers are co-prime if they share no factors apart from $1$. Hence, if a prime number $P$ is not co-prime with an $n$ such that $$1 < n < P$$ then that means that one of the factors of $n$ is a factor of $P$, which cannot be the case because $P$ is prime. This seemed to make sense to me but I wanted to double-check. I ask this because I was looking at alternate ways to fix the modulo bias in the Fisher-Yates shuffle and I think that if this is the case then I can do it.

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, that's true. Your proof is also correct.

(Making a community wiki post to get this question out of the unanswered queue without "taking credit" for the answer.)