# Operations

===

###### tags: `GeneralMath`

An *operation* on a set
1. takes two elements from that set
2. returns an element from that set

## Examples

* **Addition** is an operation on the set of positive integers
* **Addition** is an operation on the set of rational numbers
* **Addition** is an operation on the set of real numbers
* **Subtraction** is an operation on the set of real numbers
* **Multiplication** is an operation on the set of real numbers
* **Maximum** (taking the larger of the two numbers) is an operation on the set of integers. *Example:* Max(2,3) = 3
* **Concatenation** is an operation on the set of all strings with English letters. *Example 1*: Concatenation("fizz","bop") = "fizzbop". *Example 2:* Concatenation ("bop", "fizz") = "bopfizz"
* I've just made up my own operation: "for two integers $x$ and $y$, return 2*x + 3*y". We can call it *DTA* for *DoubleTripleAdd*. *Example 1:* DTA(4,5) = 8 + 15 = 23. *Example 2:* DTA(5,4) = 10 + 12 = 22.

## Can Anything Be an Operation?

**YES - as long as it satisfies the two properties listed in the definition above.**

### Some Examples of Things That Are Not Operations

* Division is **not** an operation on the set of real numbers. Dividing 2 by 0 is undefined.
* Subtraction is **not** an operation on the set of positive integers. $2 - 3 = -1$, and $-1$ is not an element of the set of positive integers.

## Identity Elements for Operations

**Definition**: An *identity element* is a special type of element: when you perform an operation with the identity element as one of the inputs, you always get the other element.

### Examples
*For the operation, "addition on the real numbers", the number 0 is the identity element. No matter what number $x$ you select, $0 + x = x$. It also works the other way: $x + 0 = x$.
* For the operation "multiplication on the positive integers", the number 1 is the identity element: $1 \cdot x = x \cdot 1 = x$, no matter what $x$ is.
* For the operation, "multiplication on the even integers", there is no identity element.
* For the operation "maximum on the nonnegative real numbers", 0 is the identity element.

### Inverse Elements

If an operation on a set has an identity element, then *some* of the elements in that set *may* have inverse elements for the operation. This is something that you have to check carefully by thinking about the elements and the operation.

#### Examples

1. For addition on the set of positive integers,
* there is no identity element,
* so there are no inverse elements.

2. For addition on the set of **non-negative** integers (now including both positive and 0),
* $0$ is the identity element
* $0$ is its own inverse
* no other element has an inverse element

3. For addition on the set of **all** integers,
* $0$ is the identity element
* to find the inverse of an element, switch the sign.
* **Example:** $-2$ is the inverse of $2$ for addition on the integers.
* **Example:** $-3$ is the inverse of $3$ for addition on the integers.

4. For multiplication on the integers,
* 1 is the identity element.
* 1 is its own inverse.
* $-1$ is also its own inverse.
* No other element in the integers has a multiplicative inverse in the integers. For instance, $2 \cdot \frac{1}{2} = 1$, but $\frac{1}{2}$ is not an integer.

5. For multiplication on the real numbers,
* 1 is the identity element.
* $0$ does not have an inverse element for multiplication. (This is why "thou shalt not divide by 0.")
* for any other number $x$, $\frac{1}{x}$ is the multiplicative inverse. For instance, $\pi$ and $\frac{1}{\pi}$ are multiplicative inverses.

6. For the operation of **Maximum** on the nonnegative integers,
* $0$ is the identity element.
* $0$ is its own inverse.
* no other number has an inverse. I can't find a value of :smiley: to **MAX(7, :smiley:) = 0*, which is what I would need if 7 had an inverse for the **Maximum** operation.

## Modular Arithmetic

When we look at the integers $\pmod{n}$ or *modulo n*, we are only concerned with the division after remainder by $n$.

**Two numbers are considered equivalent modulo n if they differ by a multiple of *n***.

For instance,
* $7 = 4 \pmod{3}$.
* $11 = 20 \pmod{3}$.
* $9 = 15 \pmod{6}$
* $3 = -5 \pmod{8}$

This means that we can always rewrite a number modulo $n$ so it is in the set $\{0,1, 2, \ldots, n-1\}$.

### Operations on Modular Arithmetic

When we work with a set of integers modulo $n$, we have two main operations:
1. addition (mod $n$)
2. multiplication (mod $n$)

### Identity Element for Addition (mod n)

The identity element for addition mod $n$ is also 0.

For instance, working mod 5,
$3 + 0 = 3 \pmod{5}$
$0 + 3 = 3 \pmod{5}$.

### Inverse Elements for Addition (mod n)

If you are looking at an element $k$ and working modulo $n$, then the inverse element of $k$ is $n-k$.

For instance, if we look at addition modulo 11, the inverse element of $2$ is $9$. This is because
$2 + 9 = 0 \pmod{11}$
$9 + 2 = 0 \pmod{11}$

**Remember that the goal of the inverse element is to get back to the identity.**

### Identity Element for Multiplication (mod n)

This is trickier; **there is no simple formula to describe the multiplicative inverse of a number $k$ when working $\pmod{n}$. **

Here is an important **FACT:** a number only has a multiplicative inverse modulo $n$ if it is [relatively prime](https://en.wikipedia.org/wiki/Coprime_integers) to $n$.

**Example 1:** For instance, if we are working $\pmod{12}$, we can look at the numbers that are relatively prime to 12:
* 1, 5, 7, 11

Each of these numbers will have a multiplicative inverse.
* $1 \cdot 1 = 1 \pmod{12}$
* $5 \cdot 5 = 25 = 1 \pmod{12}$
* $7 \cdot 7 = 49 = 1 \pmod{12}$
* $11 \cdot 11 = 121 = 1 \pmod{12}$

**It turns out that in this case, each of these numbers is its own multiplicative inverse! This is <span style = "color:red"> NOT </span> always the case.**

**Example 2:** When we work modulo 15, we have the following numbers that have multiplicative inverses (because they are relatively prime to 15):
-- 1, 2, 4, 7, 8, 11, 13

**Calculations:**

* $1 \cdot 1 = 1 \pmod{15}$
* $ 2 \cdot 8 = 16 = 1 \pmod{15}$
* $ 4 \cdot 4 = 16 = 1 \pmod{15}$
* $ 7 \cdot 13 = 121 = 1 \pmod{15}$
* $ 11 \cdot 11 = 121 =1 \pmod{15}$

So, for instance, 7 and 13 are multiplicative inverses modulo 11.