0
$\begingroup$

This is probably painfully obvious but I wanted to confirm if there's any difference between requiring that the $gcd(a,N)=1$ or $N \not\mid \!\!\;a $ if N is prime? That is, could you use either requirement and achieve the same result?

$\endgroup$
  • 1
    $\begingroup$ Can you prove it? $\endgroup$ – Jihoon Kang Jul 17 at 17:08
  • $\begingroup$ only difference is the time you need to type this in $\LaTeX$ ;) $\endgroup$ – Luis Felipe Jul 17 at 17:15
2
$\begingroup$

There is no difference, each requirement implies the other. If $\gcd(a,N)=1$ then obviously $N$ can't divide $a$ because otherwise $N$ would be a common divisor of $a,N$ which is bigger than $1$.

Now suppose $N$ does not divide $a$. Let $d$ be a positive common divisor of $a,N$. Since $N$ is prime we know $d=N$ or $d=1$. But $N$ does not divide $a$, hence $d=1$. So $1$ is the only positive common divisor of $a,N$, hence it is the $\gcd$.

$\endgroup$
  • $\begingroup$ Again forgive naiveté: "Since 𝑁 is prime we know 𝑑=𝑁 or 𝑑=1." Why do we know that 𝑑=𝑁 or 𝑑=1 if 𝑁 is prime? Why couldn't 𝑑=𝑎 or 𝑑=1 so 1 is the only positive common divisor of 𝑎,𝑁, hence it is the gcd? $\endgroup$ – JohnGalt Jul 17 at 17:21
  • 1
    $\begingroup$ What is a prime number? $N$ is prime if its positive divisors are $1$ and $N$. $\endgroup$ – Mark Jul 17 at 17:48
1
$\begingroup$

Negate: $ $ prime $\, \color{#c00}{p\mid a} \iff p\mid a,p\iff \overbrace{p\mid (a,p)\iff \color{#c00}{(a,p)\neq 1}}^{\textstyle \hphantom{p\mid (a,p)} \ {\Longleftarrow\ \ (a,p)\mid p}}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.