2
$\begingroup$

The classes of even and odd numbers has many uses, and we can find rules about combining them.

An odd number added to another odd number always yields an even number. Even + even = even. Odd + even = odd.

You can get rules for these three cases for multiplication too, and even exponentiation.

So let's try it for triples. By that I mean lets divide the non-negative integers into three classes, evenly spaced apart. I don't want to use the terms "even" and "odd" and something else, because I don't want to confuse the real even and odd numbers. So I'll just use colors.


0, 3, 6, 9, 12, ... are green.

1, 4, 7, 10, 13, ... are blue.

2, 5, 8, 11, 14, ... are red.


Addition rules.

Green + green = green.

Green + blue = blue.

Green + red = red.

Blue + blue = red.

Blue + red = green.

Red + red = blue.


Multiplication rules.

green * green = green.

green * blue = green.

green * red = green.

blue * blue = blue.

blue * red = red.

red * red = blue.


Exponentiation rules.

green ^ 0 = 1 (blue)

green ^ non-zero-green = green

green ^ blue = green

green ^ red = green

blue ^ green = blue

blue ^ blue = blue

blue ^ red = blue

red ^ non-zero-green = red or blue (2^3 is red, 2^6 is blue)

red ^ blue = blue or red

red ^ red = blue or red


So there are lots of interesting things I could point out about these results. The addition rule results are spread evenly among the colors, but the multiplication results are not. And the exponentiation results are fairly odd.

(You can also imagine doing this for any number of colors. It might take a while, but computers can speed this up easily. A good way to test for green, blue, red, is to just take x mod 3, which is like looking at the remainder of x / 3. Remainder = 0 is green, 1 is blue, 2 is red.)

But my main questions are, Has this sort of thing ever been studied before? What is its official name? Where can I read more about it? Is it significant or useful for anything?

I especially want to know if they are significant for proofs. For example, even and odd numbers are helpful in the proof by infinite descent that square root of 2 is irrational

$\endgroup$
  • 3
    $\begingroup$ What you are discovering here is modular arithmetic. However, be careful that exponential does not work nicely in general, as you have already observed. An even more general related notion is a quotient ring. $\endgroup$ – lEm May 6 at 15:44
3
$\begingroup$

This is very much doable, and actually commonly done (except you need some more care with the exponentiation).

This is, in general, called modular arithmetic. The classic introductory example (at least as long as we only care about addition) is a clockface, which has $12$ classes of numbers: $$ 0,12,24,\ldots\\ 1, 13, 25, \ldots\\ \vdots\\ 11, 23, 35, \ldots $$ We see that, for instance, if the current time is $2$, and we wait 14 hours, the clock will show the same as if we waited just $2$ hours. And so on. This is exactly the same pattern as the one you have seen with $2$ and $3$ classes, and it can be done with any number.

There is some notation associated with this. We tend to stick with numbers, because that's what we're building them from. And say we stick with your 3-class example. To signify that $4$ and $1$ are not (necessarily) the same number, but the same class, we write that as $4\equiv 1\pmod 3$. The $\equiv$ (pronounced "is congruent to") because $=$ is not technically correct as mentioned, and $\pmod 3$ (pronounced "modulo $3$") to remind ourselves that there are three classes at work here. Since everything here is done $\pmod 3$ anyways, I will skip that part here.

This way we get $$ 0+0 = 0\\ 0+1 = 1\\ 0+2 = 2\\ 1+1 = 2\\ 1+2 = 3\equiv 0\\ 2+2 = 4\equiv 1 $$ and for multiplication $$ 0\cdot 0 = 0\\ 0\cdot 1 = 0\\ 0\cdot 2 = 0\\ 1\cdot 1 = 1\\ 1\cdot 2 = 2\\ 2\cdot 2 = 4\equiv 1 $$ Then we get to exponentiation, and this is where we need some more care. Remember that exponentiation (at least with positive integer exponents) means repeated multiplication. So a priori, it doesn't make sense to use classes for the exponents. However, it turns out that as long as the number of classes we have is prime, then using classes for exponents works, and the number of relevant classes for exponents is one less than that prime (this is one form of the result known as Fermat's little theorem). So in our case, we have $3-1 = 2$ classes for the exponents. We get $$ x^{\text{odd}} \equiv x\\ x^{\text{even}}\equiv x\cdot x $$ From here there is a lot of theory one can get into. For instance, Fermat's little theorem generalizes to Euler's theorem (and Carmichael's theorem), letting you analyze large exponents efficiently. There is the Chinese Remainder theorem, which relates $\pmod{ab}$ with the combination of $\pmod a$ and $\pmod b$ (for instance, $\pmod{12}$ alone is equivalent to $\pmod 3$ and $\pmod 4$ combined; if you know that a number is congruent to $1$ modulo $3$ and to $3$ modulo $4$, then it is necessarily congruent to $7$ modulo $12$). And on the basis of this, much can be done.

Most concretely, nearly all online encryption is done using modular arithmetic. One example is the Diffie-Hellman algorithm, which lets two computers securely agree on a shared secret even if someone is listening in on all the traffic between them. Another is the RSA algorithm, which is one of the simplest (and most ubiquitous) ways of public-key, secret-key encryptions.

It is also often a very nice tool when looking for integer solutions to equations. For instance, are there integers $x, y$ such that $x^2 = 3y^2 + 2$? Not easy to solve directly, but modulo $3$, the $3y^2$ term vanishes (multiplying by $3$ is the same as multiplying by $0$), and it's easy to check that no square can be congruent to $2$ modulo $3$. So that equation has no integer solutions.

So all in all, it is a very common tool throughout several mathematical fields, and there is a lot of theory to learn here.

$\endgroup$
  • $\begingroup$ To whoever downvoted: What could I do to make this answer helpful? $\endgroup$ – Arthur May 8 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.