How can $4 \cdot 7=28=1 \bmod 9$?

Question

I was reading this article about RSA that « reader who only has a beginner level of mathematical knowledge should be able to understand » but I must be really quite dumb because I couldn't figure out that part :

Lets work in the set $\mathbb{Z}_9$, then $4 ∈ \mathbb{Z}_9$ and $gcd(4,9)=1$. Therefore $4$ has a multiplicative inverse (written $4^{−1}$) in $\bmod 9$, which is $7$. And indeed, $4⋅7=28=1 \bmod 9$.

1. Isn't $4^{-1} = ¼ \neq 7$? Or does the « in $\bmod 9$ » affect the result in a way that wasn't explained?
2. How does $28 = 1 \bmod 9$ ? Isn't $1 \bmod 9 = 1 \neq 28$ ?

Answer 1

1. When we say $4^{-1}$ here, we are referring to an inverse operation on $\mathbb Z_9$
2. $28 = 3 \times 9 + 1$

EDIT

Notice you could think that the operation $\circ$ we define here is: $a \circ b = (a \times b) \pmod 9$ (you need to mod the result by $9$ for this quotient space)

Answer 2

When we say "mod" 9, what we mean is we are working with the integers modulo 9. This means that we are working with the set of integers, but we are defining an equivalence relation $\sim$ such that $a\sim b$ iff $9\mid a-b$. Note that $9|a-b$ is read "$9$ divides $a-b$" and means there is some integer $n$ such that $9n=a-b$. You should check that this defines are equivalence relation https://en.wikipedia.org/wiki/Equivalence_relation.

Thus, when we say $28\equiv 1\mod 9$, what we mean is that $28$ and $1$ are in the same equivalence class - i.e. $9|28-1$ (which is true because 3\cdot 9=27=28-1$).

Now, a less formal way of thinking about this is as "clock arithmetic". On the clock, when you reach the 12th hour, you don't continue onto hour 13, you loop back around to 1. This is same as saying $12$ and $0$ are in the same equivalence class, and $1$ and $13$ are the same equivalence class (but a separate one from $12$ and $0$). This is a model of $\mathbb{Z}_{12}$, but you could think of $\mathbb{Z}_9$ as a 9 hour clock. Where you mark the 28th hour on a 9 hour clock? As mentioned above, it will be 1, because they are in the same equivalence class.

Multiplicative inverses in modular arithmetic must still be integers, but $a^{-1}$ is any integer $b$ such that $ab\equiv 1\mod 9$.

Answer 3

$28 = 1 \ mod \ 9$, because when you divide $28$ by $9$, you are left with a remainder of $1$ ($28 = 3*9 + 1$). As another example: $16 = 7 \ mod \ 9$, since $16 = 1*9 + 7$

So: notice that any integer divided by $9$ will have a remainder of $0$ through $8$. As such, we can define $\mathbb{Z}_9 = \{ 0,1,2,3,4,5,6,7,8 \}$, and when we multiply these numbers and take the result $mod \ 9$, the result will always be an element that is in $\mathbb{Z}_9$ itself, e.g. $5*3 = 15 = 6 \ mod \ 9$, and so we say $5 * 3 = 6$ in this 'system' $\mathbb{Z}_9$.

The inverse of an element $a$ is an element $a^{-1}$ such that $a * a^{-1} = 1$. In , $\mathbb{Z}_9$, we have $4*7=28=1 \ mod \ 9$, and so $7$ is indeed an inverse of $4$. $\frac{1}{4}$ is not, since $\frac{1}{4}$ is not a member of $\mathbb{Z}_9$.

Answer 4

$28$ is considered the same as $1$, modulo $9$, because they're both just one unit above a multiple of $9$. (Remember that $0$ is a multiple of $9$, because it's $9\times 0$). Think of a clock, and how 13:00 is the same as 1:00, because they're both just above a multiple of 12:00. Similarly, if someone were to say 25:00, that would also be 1:00. Clocks work modulo $12$.

In the usual number system, if you want to multiply $4$ by something and get $1$, you have to multiply it by $\frac14$. However, modulo $9$, we can multiply $4$ by $7$, and get something equivalent to $1$. Thus, $7$ counts as a reciprocal for $4$, but only in the mod $9$ system.

Answer 5

Modular arithmetic doesn't work exactly the same way as regular arithmetic.

Let's focus specifically on $\mod 9$. When you have expressions of the form $a \mod 9$, these expressions can evaluate to one of only 9 numbers: $$0,1,2,3,4,5,6,7,8$$ How do we find the value of an expression like $a \mod 9$? The value of $a \mod 9$ is the remainder you get when you divide $a$ by $9$. For example, $12 \mod 9$ is $3$ because $12 \div 9$ is $1$ with a remainder of $3$.

Another, more common, way of writing this fact is $3 \equiv 12 \mod 9$. We read this as "three is congruent to 12 modulo 9." Note that we can also write it as $12 \equiv 3 \mod 9$. They are two slightly different ways of saying exactly the same thing. The two different ways are really just slightly different ways of asking the same thing:

$$12 \equiv x \mod 9 \qquad\qquad \text{Solve for $x$}$$ $$x \equiv 12 \mod 9 \qquad\qquad \text{Solve for $x$}$$

I believe the first way is more common. It's understood that when we say "solve for $x$ if $12 \equiv x \mod 9$" (that is, when we say "$12$ is congruent to what number $x$ modulo 9?"), that we implicitly want $x$ to be one of the numbers $0,1,2,3,4,5,6,7,8$.

For your specific questions:

Isn't $4^{-1} = ¼ \neq 7$? Or does the « in $mod$ $9$ » affect the result in a way that wasn't explained?

In $\Bbb Z_9$, $4^{-1}$ is the number $x$ such that $4x \equiv 1 \mod 9$. Note that this is equivalent to saying $1 \equiv 4x \mod 9$. This means that when we divide $4x$ by $9$, we get a remainder of $1$. Therefore $4x$ must be $1$ larger than a multiple of $9$. Since $x$ must be one of $0,1,2,3,4,5,6,7,8$, then we must ask ourselves, "what number is divisible by $4$, is one larger than a multiple of $9$, and gives me one of $0,1,2,3,4,5,6,7,8$ when I divide it by $4$?" The answer is $28$, because $28 = 27 + 1$ and $28/4 = 7$. Therefore $7 = 4^{-1}$ in $\Bbb Z_9$.

Another way to find a modular inverse, especially if the set is small enough (which $\Bbb Z_9$ certainly is), is to just do trial and error. We want $x$ such that $4x \equiv 1 \mod 9$, and we know $x$ must be one of $0,1,2,3,4,5,6,7,8$. So we can just check these values one-by-one, and we'll see that $7$ is the only one that works.

How does $28 = 1$ $mod$ $9$ ? Isn't $1$ $mod$ $9 = 1 \neq 28$ ?

$28 \equiv 1 \mod 9$ because $28$ is $1$ more than a multiple of $9$. ($27$ is the relevant multiple of $9$ here.)

$1 \equiv 1 \mod 9$ because $1$ is $1$ more than a multiple of $9$. ($0$ is the relevant multiple of $9$ here.)

Saying two different numbers (in this case, 28 and 1) are congruent to the same number (in this case, 1) modulo $9$ (or modulo any other number) is not the same thing as saying those two numbers are the same number. In fact, there are infinitely many numbers congruent to $1 \mod 9$. Specifically, they are $1, 10, 19, 28, 37, 46, 55, 64, \dots$. Note that negative numbers can also be congruent to $1 \mod 9$, like $-8, -17, -26, \dots$. All these negative numbers are $1$ larger than some multiple of $9$ (e.g., $-17 = -18 + 1 = 9 \cdot(-2) + 1$).

Answer 6

Notice that $$7 \times 4 = 28 = 3(9)+1 \equiv 1 \mod 9$$

Since $7 \times 4 \equiv 1 \mod 9$

We say that $7$ is the multiplicative inverse of $4 \mod 9$.

We denote it via $$4^{-1} \equiv 7 \mod 9$$

Answer 7

You are familiar with “$\bmod$” as an operation $ℤ × ℤ → ℤ$, that is: For any two integers $x, n$, you understand $x \bmod n$ to be the unique remainder within $0, …, n-1$ from a division of $x$ by $n$.

You seem to be missing the general concept of modulo arithmetic. In (elementary, integer) modulo arithmetic, you fix an integer $n$, called modulus, and are working with a version of the integers $ℤ$ in which you regard any two integers that differ by a multiple of $n$ as the same. That version is named $ℤ/nℤ$ (“$ℤ$ modulo $nℤ$”).

The notation that states that two integers $x, y$ differ by some multiple of $n$ also uses “mod”, and is $$“x \equiv y \mod n” \quad \text{or}\quad “x = y \mod n.”$$

Now, $28 = 3·9 + 1$, so $28 = 1 \bmod 9$. (Or “$28 = 1$ in $ℤ/9ℤ$.”)

By the same reasoning, even more is true, for example: $$1 = 10 = 28 = 37 = - 8 = … \bmod 9,$$ although neither $28$ nor $37$ is a remainder from a division by $9$. So this is different from thinking of $\bmod$ as an operation. Think of it as a silly game and read it as

$1 = 10 = 28 = 37 = -8 = …$, when regarding $9$ as $0$.

(You can also see from that that $ℤ/9ℤ$ has exactly nine elements, which are represented by $0, …, 8$. All other integers are equal to one of them modulo $9$.)