Factorising a large number, part II: Gaussian integers

You know how things escalate on Twitter sometimes? Somebody makes an off-hand comment wondering whether a number is prime and suddenly you're neck deep in number theory?

This is the story of how you might factorise 842,909 on paper.

In fact, it's the second part of the story; we join it after having discovered that 842,909 can be written as $850^2 + 347^2$ and as $875^2 + 278^2$.

The Gaussian integers

If those +s were -s, we'd be laughing: we could simply apply the difference of two squares to either and boom! A factorisation. However, we don't have that - at least, not in the positive integers.

However, in the Gaussian integers, we do. Gaussian integers are the extension of the integers into complex numbers: they're complex numbers of the form $a+b\i$ where both $a$ and $b$ are integers.

Gaussian integers have many neat properties, but among the neatest is that they are - like the integers - a unique factorisation domain. Any Gaussian integer can, essentially1, be decomposed into one set of prime factors. Primes, though, are funny things: numbers of the form $4n+3$ or $(4n+3)\i$ are primes if $4n+3$ is prime; otherwise, Gaussian primes take the form $a + bi$ with $a^2 + b^2$ being a prime not of the form $4n+3$, with neither $a$ nor $b$ being zero. For example, $5 + 2\i$ is a Gaussian prime, because $a^2 + b^2 = 29$, a prime that's one more than a multiple of 4. Also, $-1-\i$ is a Gaussian prime, because $a^2 + b^2 = 2$, a prime that's not in the form $4n+3$. Clear enough?

In particular, our number - one more than a multiple of 4, but with $b=0$ - is not a Gaussian prime. In fact, having written our number as the sum of two squares in two different ways, we know it has factors in the Gaussian integers of $(850\pm347\i)$ and $(875 \pm 278\i)$.

How does this help?

The key thing is that the Gaussians are a unique factorisation domain - we have two distinct factorisations of our number, which means that these factors are not prime.

Suppose $850+347\i = g_1 g_2$, where $g_1$ and $g_2$ are Gaussian integers and $g_1$ also divides $875+278\i$. We know such numbers exist. Because $850-347\i$ is its complex conjugate, this must be $\bar{g_1} \bar{g_2}$.

We can also state that $875 + 278\i = g_1 g_3$ and $875 - 278\i = \bar{g_1}\bar{g_3}$ for some further Gaussian integer $g_3$.

Now the clever bit: if we work out $(850+347\i)(875-278\i)$, we get $g_1 \bar{g_1} g_2 \bar{g_3}$ - and $g_1 \bar{g_1} = |g_1|^2$, an integer that's a factor of our original number!

This works out to be $840,216 - 67,325\i$ - and if we apply the Euclidean algorithm to the two components, we'll find $|g_1|^2$!

The Euclidean algorithm

The Euclidean algorithm finds the greatest common factor of two numbers by repeatedly taking multiples of one away from the other, as follows:

• $840,216 = 12 \times 67,325 + 32,316$
• $67,325 = 2\times 32,316 + 2,693$
• $32,316 = 12 \times 2,693$ exactly

This gives 2,693 as a factor of our original number - in fact, it's $2,693 \times 313$.

Aharr!

"You could just put it into Wolfram Alpha, though, couldn't you, me hearty?"

But where's the fun in that?

* Many thanks to Hilarie Orman and Richard Schroeppel for piquing my interest about factorising!
* Corrected a mistaken number 2018-10-15. Thanks to @teakaybee for pointing it out! Also added a link. Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

1. By which I mean, up to a power of $\i$ []

Share

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9235178,"math_prob":0.9984816,"size":3150,"snap":"2019-43-2019-47","text_gpt3_token_len":925,"char_repetition_ratio":0.13699937,"word_repetition_ratio":0.029250458,"special_character_ratio":0.32031745,"punctuation_ratio":0.11969697,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9990726,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-23T18:10:23Z\",\"WARC-Record-ID\":\"<urn:uuid:bcb49b45-9972-4bc8-b65b-f7a8a986178d>\",\"Content-Length\":\"60463\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2208592f-d048-4949-afd5-6b160e4809ec>\",\"WARC-Concurrent-To\":\"<urn:uuid:909b2f79-0a4f-439d-95e4-45374407ffc8>\",\"WARC-IP-Address\":\"185.20.49.4\",\"WARC-Target-URI\":\"http://www.flyingcoloursmaths.co.uk/factorising-a-large-number-part-ii-gaussian-integers/\",\"WARC-Payload-Digest\":\"sha1:6NRLLLNVIZGNHJCMQFNUMO3FP7WZ7FDW\",\"WARC-Block-Digest\":\"sha1:JKQGSWZECLW4FQBJ3YR6YTELW2NJTOME\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570987835748.66_warc_CC-MAIN-20191023173708-20191023201208-00531.warc.gz\"}"}