Co-prime or Not Co-prime?
⎩ ⎪ ⎨ ⎪ ⎧ a b c = = = 1 0 0 + 8 5 i 2 0 8 + 3 9 i 1 8 8 + 2 2 i
Given that a , b , c are Gaussian integers shown above, if d is the greatest common divisor (GCD) of a , b , c , what is the value of ∣ d ∣ 2 ?
The answer is 689.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Moderator note:
This begs the question. Is it true that for complex numbers z i , if we define z = g cd ( z 1 , z 2 , … , z n , then we have ∣ z ∣ 2 = g cd ( ∣ z 1 ∣ 2 , ∣ z 2 ∣ 2 , … , ∣ z n ∣ 2 ) .
Why, or why not?
Since 6 8 9 = 1 3 × 5 3 = ( 3 + 2 i ) ( 3 − 2 i ) ( 7 + 2 i ) ( 7 − 2 i ) , and since 3 ± 2 i and 7 ± 2 i are prime in Z [ i ] (being Gaussian integers whose modulus squared is prime), the only way that 6 8 9 can be written as a 2 + b 2 , with a , b integers, is if a + i b is associate to either ( 3 + 2 i ) ( 7 + 2 i ) = 1 7 + 2 0 i or ( 3 + 2 i ) ( 7 − 2 i ) = 2 5 + 8 i . Thus we can be sure that the two representations of 6 8 9 you have given are the only ones! It is easier to spot the "sum of squares" representations of 1 3 and 5 3 than it is for 6 8 9 .
Exactly! I'm quite new to this theory and wondering if Gaussian primes can also be applied to other remainder theorem, such as Chinese remainder theorem or Fermat's little theorem.
Log in to reply
The Chinese Remainder Theorem relies on the fact that, if a , b are coprime integers, then we can find integers u , v such that a u + b v = 1 . This result holds for coprime elements in any principal ideal domain, and so certainly holds in a Euclidean domain such as the Gaussian integers.
Log in to reply
Thank you for your answer. Then I can explore more on this group of integers. :)
Yes, Fermat's little theorem works for the Gaussian integers: If p is a Gaussian prime and n is the number of Gaussian integers mod p , then a n − 1 ≡ 1 ( m o d p ) for non-zero a . The proof is the same as for the integers.
The Chinese Remainder Theorem is a very general (and somewhat superficial) result that, properly phrased (in terms of ideals), applies to all rings.
Log in to reply
Thank you for your reply. It is an interesting field to study indeed. :)
Log in to reply
@Worranat Pakornrat – Now what about Euler's totient function? ;)
Log in to reply
@Otto Bretscher – I read about it, too, though I haven't given much thought for it yet. Doctors don't really have time for their own. :(
Quite the same solution.
To the Challenge Master: No, that equation does not hold, as the example g cd ( 2 + i , 1 + 2 i ) = 1 shows.
The square moduli of the three given numbers are 1 0 0 2 + 8 5 2 = 1 7 2 2 5 , 3 5 8 2 8 , and 4 4 7 8 5 , with greatest common divisor 6 8 9 . Testing the two representations of 6 8 9 as the sum of two squares, 6 8 9 = 8 2 + 2 5 2 = 1 7 2 + 2 0 2 , we observe that 2 0 + 1 7 i is a common divisor of the three given numbers.