modular calculus, find all solutions in ℤ

_rob

New member
Joined
Nov 28, 2018
Messages
8
How do I go about solving something like this:

Find all the solutions in ℤ / 80ℤ of the equation
4x + 5 ≡ 1 mod 80

Now obviously x must be -1 for the equation to hold true, but I don't know what to do about the "Find all the solutions in ℤ / 80ℤ" part.

Another similar one:
Find all the solutions in ℤ / 28ℤ of the equation.
4x – 24 = 0

Here x must obviously equal 6, but again I don't know what to do about "Find all the solutions in ℤ / 28ℤ".
 

ksdhart2

Senior Member
Joined
Mar 25, 2016
Messages
1,152
It seems like it would be wise for you to brush up on the idea of what modular arithmetic is and what it really means. It's true that x = -1 would be the only solution to the equation \(4x + 5 = 1\), and likewise x = 6 would be the only solution to the equation \(4x - 24 = 0\) if you were working under the "normal" rules of arithmetic, but that's not what's being asked here.

The notation \(\displaystyle \frac{\mathbb{Z}}{N\mathbb{Z}}\) means you're working in a ring where you only have access to the integers \(0, 1, 2, \cdots, N-1\) and when you would reach \(N\), you "roll over" and begin again at 0. So, if you were doing some workings and you found an answer of 27 but you were working in \(\displaystyle \frac{\mathbb{Z}}{8\mathbb{Z}}\), you'd have to find what element 27 is congruent to... 27 - 8 = 19, 19 - 8 = 11, 11 - 8 = 3, so we say that \(27 \equiv 3 \: (\text{mod} \: 8)\)

As a full example of this concept, consider finding all solutions to \(3x + 2 = 2\) in \(\displaystyle \frac{\mathbb{Z}}{6\mathbb{Z}}\). As a visual means of further demonstrating the idea, let's manually substitute in each value \(0, 1, 2, \cdots, 5\), and see what we get:

\(\displaystyle 3(0) + 2 \equiv 2 \: (\text{mod} \: 6)\)
\(\displaystyle 3(1) + 2 \equiv 5 \: (\text{mod} \: 6)\)
\(\displaystyle 3(2) + 2 \equiv 2 \: (\text{mod} \: 6) \: \: \: {\color{red} \textit{3(2) + 2 = 8, but 8 is not an element of the ring, so we "reduce" it to one that is}}\)
\(\displaystyle 3(3) + 2 \equiv 5 \: (\text{mod} \: 6) \: \: \: {\color{red} \textit{3(3) + 2 = 11, but 11 is not an element of the ring, so we "reduce" it to one that is}}\)
\(\displaystyle 3(4) + 2 \equiv 2 \: (\text{mod} \: 6)\)
\(\displaystyle 3(5) + 2 \equiv 5 \: (\text{mod} \: 6)\)

Now you give it a try. It happens to be true in both cases that the solution under "normal" arithmetic is also a solution in the new ring, but are there other solutions to these modular equations? What might they be?
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
8,331
Find all the solutions in ℤ / 80ℤ of the equation
4x + 5 ≡ 1 mod 80
Now obviously x must be -1 for the equation to hold true, but I don't know what to do about the "Find all the solutions in ℤ / 80ℤ" part.
Here are hints by way of additional solutions: \(\displaystyle x=79~\&~x=-81\) HERE is a tool that might help.
Now think about why that is.
 

_rob

New member
Joined
Nov 28, 2018
Messages
8
Here are hints by way of additional solutions: \(\displaystyle x=79~\&~x=-81\) HERE is a tool that might help.
Now think about why that is.
Thanks, so while the upper bound is limited to 80-1, the lower bound is not? So you can keep recursively subtracting 80 from -1 to negative infinity? So -241 and -161 are also solutions?
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,156
Actually, the numbers -1 and 79 and so on are all the same solution in Z/(80Z) -- they are congruent mod 80, so they are not considered different.

The more important thing is that there are other solutions mod 80 -- numbers not congruent to -1 that are also solutions. This comes about because there are numbers other than -1 that you can multiply by 4 to get -4 (mod 80). (Can you find them?) Your claim that it is "obvious" that x must be -1 was wrong.

What have you learned about modular arithmetic and solving equations?
 
Top