Understanding the Results of gcd(x,n)

[Peter_Newman]

Hello,

I read something about to which I have a small question of understanding. Before I would like to outline it a little. So we have the primes $p$ and $q$ and we know $p|x$ and $n = p\cdot q$ furthermore it follows that $p|n$ also holds.

Now it was said that if $p|x$, then $\gcd(x,n)$ is either $n$ or $p$. Why is this so? I had a few thoughts that I would like to share here.

Consideration 1:
From $p|x$ it follows that there is a $c$ such that $c \cdot p = x$, I simply put this into the $\gcd(x,n)$ and rewrite this a bit, I get $\gcd(c\cdot p, p\cdot q)$. This is exactly $n$ if the $c=q$, because $c$ cannot divide either the $q$ or the $p$. (gcd of two equal numbers, is that number)

Consideration 2:
I again use the approach as before, $\gcd(c\cdot p, p\cdot q)$. So this is $p$ exactly when $c \neq q$, because then the only (common) divisor can be the $q$.

I would be interested to know if the reasoning is correct.

 

[PeroK]

If $n = pq$ then the only divisors of $n$ are $1,p, q, pq$.

Then the two cases are whether $q$ divides $x$ or not.

It's not a case of $c =q$, it's a case of whether $q$ divides $c$.

 

[Peter_Newman]

Hello @PeroK , can you explain this a little further? From there, it is not really clear to me, how one then comes to the assertion "if $p|x$, then $gcd(x,n)$ is either $n$ or $p$".

 

[PeroK]

Hello @PeroK , can you explain this a little further? From there, it is not really clear to me, how one then comes to the assertion "if $p|x$, then $gcd(x,n)$ is either $n$ or $p$".

I left that bit for you to do. Look at the two cases I mentioned.

 

[Peter_Newman]

OK, then I would get started:

If the $q$ does not divide the $c$, then $\gcd(cp,pq)=p$, I would argue that the $p$ is the greatest common factor (in the expression of the gcd()). Is stat okay?

 

[PeroK]

OK, then I would get started:

If the $q$ does not divide the $c$, then $\gcd(cp,pq)=p$, I would argue that the $p$ is the greatest common factor (in the expression of the gcd()). Is stat okay?

Yes.

 

[Peter_Newman]

Thank you @PeroK .

I have to admit, however, that the other part of proving "feels" kind of weird.

If the $q$ divides the $c$, then surely the $\gcd(cp,pq) = q$, but that can't be? Surely it should be shown that then the $n$ results?!

 

[PeroK]

Thank you @PeroK .

I have to admit, however, that the other part of proving "feels" kind of weird.

If the $q$ divides the $c$, then surely the $\gcd(cp,pq) = q$, but that can't be? Surely it should be shown that then the $n$ results?!

You're looking for the greatest common divisor. And $pq > q$.

Try $c = qd$ if you are still unsure.

 

[Peter_Newman]

Oh, now I see what you mean! Yes, of course that is absolutely right! If the $q$ divides the $c$ that means exactly $k\cdot q = c$... Insert and one sees the "magic". Many thanks @PeroK !