# Solve linear $\,ax + b = 0$ in $Z_N$

So I'm really struggling to tackle the above question. I don't know how to approach it at all. I'm aware that I'm trying to solve for $x$, but given $Z_n$ I'm confused.

The question is related to an assignment, but I fell ill during the time related material was discussed. So what I really would like is someone to explain how I would go about this.

I'm really not very strong with Maths at all, so this is really struggling and worrying me as it's an important piece of coursework. Could someone maybe talk me through it with an example?

The question I have uses BigIntegers and requires a programmatic approach to solve it, but I think before I even touch that I need to understand how one would solve it with much smaller numbers, so any help would be appreciated.

• Start with an example: solve $5x+1=0$ in $\mathbb{Z}/2\mathbb{Z}$. – Dietrich Burde Nov 21 '13 at 20:20
• My issue is I don't know what to do with Zn, for instance just given 5x + 1 = 0, x = -0.2. But Given Z2 I don't know what to do or how to approach it. – user110540 Nov 21 '13 at 20:25
• $\mathbb{Z}/2\mathbb{Z}$ consists of the class of odd and the class of even integers, represented by $x=0$ and $x=1$. But $x=-0.2=-1/5$ is not an even or odd integer. I guess that you have to read about the definition of $\mathbb{Z}/n\mathbb{Z}$ first. – Dietrich Burde Nov 21 '13 at 20:34
• But I really don't know where to start. I'm not even sure I know what Zn is. I thought it was a finite field as we were covering something similar, but even knowing that I still couldn't come up with a solution. For instance given 6x + 2 = 0 in Z7. I get that Z7 = {0,1,2,3,4,5,6} but what do I do with that knowledge in order to solve for x? This is where i'm lost :( – user110540 Nov 21 '13 at 20:41

a*x = -b in Zn

How to get 'a' to other side? Calculate modular multiplicative inverse. We can only do this if a and N are coprime (their greatest common denominator is 1)

x = -b*a^-1 in Zn

Remember that this is modular arithmetic and our answer should be in Zn

24x + 32 = 0 in Z64

In other words, what integer x in range Z64 solves the equation such that 24x + 32 (mod 64) = 0

We can see that 24 and 64 are not coprime so we cannot calculate the modular inverse of 24 and cannot solve it.

It's not a and b that are coprime and used to calculate the inverse, it's a and N. You can clearly see that gcd(4,6) is 2 and not 1.

4x + 9 = 0 in Z6

Z6 = {0,1,2,3,4,5}

4*0 + 9 = 9 (3)

4*1 + 9 = 13 (1)

4*2 + 9 = 17 (5)

4*3 + 9 = 21 (3)

4*4 + 9 = 25 (1)

4*5 + 9 = 29 (5)

You can see that non of these values are zero in Z6 so it cannot be solved. Try a small example where a and N are coprime to see that it can be solved.

Then find out how to calculate a modular inverse and you will be able to solve these linear equations.

• Ok, so for example. Given some equation 24x + 32 = 0 in Z64. we go to 24x = -32 in z64 then move to x = -32*24^-1 in Z64? I don't understand the importance of Z64 is where i'm really struggling. – user110540 Nov 21 '13 at 21:24
• ALright, so given two coprime numbers say 4 & 9. we get some equation 4x + 9 = 0 in Z6 Now this is easily solvable by simply guessing, but in reality I have to solve for a very large numer, I'm just wanting to undertand how I would do that So I guess the first step now is to calculate the inverse of 4? So if a = 4, its modular inverse is a^-1, now I know that I can determine if it has an inverse by using gcd. So would I now do gcd(4, 6) in order to find out if gcd = 1? – user110540 Nov 21 '13 at 21:42
• I only have the example given to me in my spec and i dont want to give those numbers as i want to solve it myself. I was just throwing numbers together, could you write a complete example? I really appreciate your time but im still really struggling. – user110540 Nov 21 '13 at 23:00

Let's work a specific example first. We will solve the equation $$5x + 4 = 0$$ in the finite field $\Bbb{Z}_7$.

Before we begin, make sure that you understand that $$\Bbb{Z}_7 = \{ [0], [1], \ldots, [6] \}$$ is the set of residue classes (a.k.a. congruence classes) modulo $7$. What does that mean? It means that we only pay attention to the remainder when an integer is divided by $7$. So, for instance, the multiples of $7$ (which give remainder $0$) all represent the same element in $\Bbb{Z}_7$. $$\cdots = [-14] = [-7] = [0] = [7] = [14] = \cdots$$ Similarly, all the numbers that are $1$ more than a multiple of $7$ represent the same element in $\Bbb{Z}_7$. $$\cdots = [-13] = [-6] = [1] = [8] = [15] = \cdots$$ And so on, for $[2], \ldots, [6]$.

A nice way to visualize $\Bbb{Z}_7$ is to picture taking the integers $\Bbb{Z}$ as points on the number line and wrapping the number line into a circle to make $0$ coincide with $7$, $14$, etc. You have, in effect, a clock with $7$ hours. Why do all the field operations still work in a consistent manner? It's a small miracle (that you can read about elsewhere).

Note: it is common to abuse notation and not include the brackets when all the arithmetic is happening in a given finite field. So from now on, I will write things like $5 = 12$, when I mean $[5] = [12]$, etc.

Now, let's solve $$5x + 4 = 0.$$

The first step: add $-2$ to both sides to obtain $$5x = -4.$$

Now we need a multiplicative inverse to $5$. This is a number $y \in \Bbb{Z}_7$ such that $$5y = 1,$$ which means that in the integers, $5y$ is $1$ more than a multiple of $7$. It's not hard to notice that $5 \cdot 3 = 15$ which leaves remainder $1$ upon division by $7$. Continuing the calculation in $\Bbb{Z}_7$: \begin{align} 5x &= -4 \\ 3 \cdot (5x) &= 3 \cdot (-4) \\ (3 \cdot 5) x &= -12 \\ x &= 2 \\ \end{align}

How does this work in general? Consider the equation $$ax = b$$ in the finite field $\Bbb{Z}_n$. If $d = \gcd(a, n)$ divides $b$, then it has solutions. Otherwise it doesn't. In particular, if $a$ and $n$ are relatively prime, then the equation always has a solution.