Understanding the Results of gcd(x,n)

  • #1
Peter_Newman
155
11
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.
 
Physics news on Phys.org
  • #2
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##.
 
  • Like
Likes Peter_Newman
  • #3
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##".
 
  • #4
Peter_Newman said:
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.
 
  • #5
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?
 
  • #6
Peter_Newman said:
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.
 
  • Like
Likes Peter_Newman
  • #7
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?!
 
  • #8
Peter_Newman said:
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.
 
  • Like
Likes Peter_Newman
  • #9
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 !
 
  • Like
Likes PeroK

Similar threads

Back
Top