Mathematics desk
< February 10	<< Jan \| February \| Mar >>	February 12 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 11[edit]

Using mod (i.e. remainder after division) on complex numbers[edit]

I'm currently trying my best to solve a Project Euler problem, and I have a question about using the mod function on complex numbers (i.e. the remainder after the division one, not the traditional "modulus" for complex numbers). One of the lovely things about mod is that it sort of "distributes" over addition and multiplication, right? Like this:

(a+b) mod m = ((a mod m) + (b mod m)) mod m

(a*b) mod m = ((a mod m) * (b mod m)) mod m

(btw, I realize that you usually don't write it like that, like an operator, but I only really have experience in computer science, so forgive my poor math-notation). First off all: this obviously applies when a and b are integers, but it also applies when they are arbitrary reals, right (at least assuming that m is an integer)?

But what if you defined the mod function for complex numbers, so that it applies to both the real and imaginary part? I.e., what if you defined it "complex mod" like this:

z = a + bi

z mod m = (a mod m) + i*(b mod m)

Does those "distributive" properties still hold? I.e., if z and v are complex numbers with the mod-function defined just like I did, is this true?

(z+v) mod m = ((z mod m) + (v mod m)) mod m

(z*v) mod m = ((z mod m) * (v mod m)) mod m

In all these examples, a and b can be arbitrary reals, but m is always a positive integer.

PS. The problem I'm working on is Problem 258, and I think I've almost cracked it. I figured out a way that would work but would take a few hours or so, but since Project Euler has an official "should run in under a minute" policy, I'm trying to figure out a better way to do it rather than just leaving the computer on over night. If anyone is curious, I'd be happy to explain why I need to take mods of complex numbers in order to solve it (or at least why I think I do, I may be completely barking up the wrong tree). 80.216.1.161 (talk) 18:52, 11 February 2012 (UTC)[reply]

Yeah, it will "distribute" in the way you want. To see this, consider how you calculate addition and multiplication of complex numbers in terms of the real and imaginary components:

(a + bi) + (c + di) = (a+c) + (b+d)i

(a + bi) * (c + di) = (ac - bd) + (ad + bc)i

Both operations can be built up with addition, subtraction and multiplication, which all behave nicely mod m as you mentioned. Rckrone (talk) 03:14, 12 February 2012 (UTC)[reply]

If you know something about rings, this setting that you are working in is the quotient ring (Z/mZ)[x]/(x² + 1). So basically we are taking the integers mod m, and then adding a new element x, which satisfies the property that x² = -1 (so x is the imaginary unit). Rckrone (talk) 03:24, 12 February 2012 (UTC) Edit: Maybe it's clearer to write the ring as Z[x]/(m, x² + 1).[reply]

BTW, Project Euler, per se, doesn't appear to have a one minute requirement, if you read all the about and problem pages then time is not mentioned anywhere. I agreed that many problem discussion threads mention folk endeavouring to achieve under 1 minute and it is probably mentioned in the discussion forums, it is too heavily dependent upon the technology used. FWIW, I solve the problems in interpreted QBASIC and am happy with solutions that run in under an hour. -- SGBailey (talk) 20:33, 12 February 2012 (UTC)[reply]

Take care: you seem to have been asking about the general case (z=a + ib, where a and b are real). It does not appear to work in this case, only for Gaussian integers. Counterexample: z = 3/4 + 3/4i. ((z² mod 1) ⋅ z) mod 1 ≠ z ³ mod 1. — Quondum ^☏✎ 17:59, 13 February 2012 (UTC)[reply]