You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an alternative browser.
You should upgrade or use an alternative browser.
Question relating to modulo
- Thread starter daza93
- Start date
Hello, daza93!
Here is a very primitive approach . . .
We have: .\(\displaystyle 81x\:\equiv\:1\text{ (mod 256)} \quad\Rightarrow\quad 81x \:=\:256a + 1\;\text{ for some integer }a\)
\(\displaystyle \text{Solve for }x\!:\;\;x \:=\:\dfrac{256a + 1}{81} \quad\Rightarrow\quad x \:=\:3a + \dfrac{13a + 1}{81}\) .[1]
Since \(\displaystyle x\) is an integer, \(\displaystyle 13a + 1\) must be a multiple of 81.
That is: .\(\displaystyle 13a + 1 \:=\:81b\:\text{ for some integer }b\)
\(\displaystyle \text{Solve for }a\!:\;\;a \:=\:\dfrac{81b - 1}{13} \quad\Rightarrow\quad a \:=\:6b + \dfrac{3b-1}{13}\) .[2]
Since \(\displaystyle a\) is an integer, \(\displaystyle 3b-1\) must be a multiple of 13.
That is: .\(\displaystyle 3b-1 \:=\:13c\:\text{ for some integer }c.\)
\(\displaystyle \text{Solve for }b\!:\;\;b \:=\:\dfrac{13c+1}{3} \quad\Rightarrow\quad b \:=\:4c + \dfrac{c+1}{3}\) .[3]
Since \(\displaystyle b\) is an integer, \(\displaystyle c+1\) must be a multiple of 3: .\(\displaystyle c\,=\,2\)
Substitute into [3]: .\(\displaystyle b \:=\:4(2) + \dfrac{2+1}{3} \quad\Rightarrow\quad b \:=\:9\)
Substitute into [2]: .\(\displaystyle a \:=\:6(9) + \dfrac{3(9) - 1}{13} \quad\Rightarrow\quad a \,=\,56\)
Substitute into [1]: .\(\displaystyle x \:=\:3(56) + \dfrac{13(56) + 1}{81} \quad\Rightarrow\quad \boxed{x \,=\,177}\)
Check: .\(\displaystyle 81(177) \:=\:14,\!337 \:=\:56(256) + 1\;\;\checkmark\)
Here is a very primitive approach . . .
\(\displaystyle \text{Find a value for }x\text{ which satisfies: }\:81x\:\equiv\:1\text{ (mod 256)}\)
We have: .\(\displaystyle 81x\:\equiv\:1\text{ (mod 256)} \quad\Rightarrow\quad 81x \:=\:256a + 1\;\text{ for some integer }a\)
\(\displaystyle \text{Solve for }x\!:\;\;x \:=\:\dfrac{256a + 1}{81} \quad\Rightarrow\quad x \:=\:3a + \dfrac{13a + 1}{81}\) .[1]
Since \(\displaystyle x\) is an integer, \(\displaystyle 13a + 1\) must be a multiple of 81.
That is: .\(\displaystyle 13a + 1 \:=\:81b\:\text{ for some integer }b\)
\(\displaystyle \text{Solve for }a\!:\;\;a \:=\:\dfrac{81b - 1}{13} \quad\Rightarrow\quad a \:=\:6b + \dfrac{3b-1}{13}\) .[2]
Since \(\displaystyle a\) is an integer, \(\displaystyle 3b-1\) must be a multiple of 13.
That is: .\(\displaystyle 3b-1 \:=\:13c\:\text{ for some integer }c.\)
\(\displaystyle \text{Solve for }b\!:\;\;b \:=\:\dfrac{13c+1}{3} \quad\Rightarrow\quad b \:=\:4c + \dfrac{c+1}{3}\) .[3]
Since \(\displaystyle b\) is an integer, \(\displaystyle c+1\) must be a multiple of 3: .\(\displaystyle c\,=\,2\)
Substitute into [3]: .\(\displaystyle b \:=\:4(2) + \dfrac{2+1}{3} \quad\Rightarrow\quad b \:=\:9\)
Substitute into [2]: .\(\displaystyle a \:=\:6(9) + \dfrac{3(9) - 1}{13} \quad\Rightarrow\quad a \,=\,56\)
Substitute into [1]: .\(\displaystyle x \:=\:3(56) + \dfrac{13(56) + 1}{81} \quad\Rightarrow\quad \boxed{x \,=\,177}\)
Check: .\(\displaystyle 81(177) \:=\:14,\!337 \:=\:56(256) + 1\;\;\checkmark\)
^ That certainly works well enough.
Here's an approach using 3 and Euclid's algorithm. Note, this turned out to be "easy" right away. The idea is to continue the algorithm until you get "1" and reverse it.
\(\displaystyle 256 = 3(85) + 1\) so,
\(\displaystyle 256 + 3(-85)= 1 \)
Now, mod 256 this says that \(\displaystyle 256 + 3(171) = 1\) and so \(\displaystyle 3(171) \equiv 1 (\text{mod 256})\)
Hence \(\displaystyle 81(171^4) \equiv81(177) \equiv 1 (\text{ mod 256})\), i.e., \(\displaystyle x=177\)
---
Now, if we didn't have that \(\displaystyle 81=3^4\) we would have more work to do, so I will do it that way.
\(\displaystyle 256 = 81(3) + 13\)
\(\displaystyle 81 = 13(6) + 3\)
\(\displaystyle 13 = 3(4) + 1\)
Now we go backwards (never multiply out any 81s or 256s going backwards, we want a linear combination):
(3): \(\displaystyle 1= 13-3(4)\)
(2): \(\displaystyle 3= 81-13(6)\)
(1): \(\displaystyle 13 = 256-81(3)\)
Plug (2) into (3)
(4): \(\displaystyle 1= 13-[81-13(6)](4) = (-4)81+(25)13\)
Plug (1) into (4):
\(\displaystyle 1 = (-4)(81) + 25[256-81(3)] = 256(25) + 81(-79)\)
Therefore \(\displaystyle 81(-79)\equiv 1 (\text{ mod } 256)\), and of course \(\displaystyle -79 \equiv 177\)
This always works...
Here's an approach using 3 and Euclid's algorithm. Note, this turned out to be "easy" right away. The idea is to continue the algorithm until you get "1" and reverse it.
\(\displaystyle 256 = 3(85) + 1\) so,
\(\displaystyle 256 + 3(-85)= 1 \)
Now, mod 256 this says that \(\displaystyle 256 + 3(171) = 1\) and so \(\displaystyle 3(171) \equiv 1 (\text{mod 256})\)
Hence \(\displaystyle 81(171^4) \equiv81(177) \equiv 1 (\text{ mod 256})\), i.e., \(\displaystyle x=177\)
---
Now, if we didn't have that \(\displaystyle 81=3^4\) we would have more work to do, so I will do it that way.
\(\displaystyle 256 = 81(3) + 13\)
\(\displaystyle 81 = 13(6) + 3\)
\(\displaystyle 13 = 3(4) + 1\)
Now we go backwards (never multiply out any 81s or 256s going backwards, we want a linear combination):
(3): \(\displaystyle 1= 13-3(4)\)
(2): \(\displaystyle 3= 81-13(6)\)
(1): \(\displaystyle 13 = 256-81(3)\)
Plug (2) into (3)
(4): \(\displaystyle 1= 13-[81-13(6)](4) = (-4)81+(25)13\)
Plug (1) into (4):
\(\displaystyle 1 = (-4)(81) + 25[256-81(3)] = 256(25) + 81(-79)\)
Therefore \(\displaystyle 81(-79)\equiv 1 (\text{ mod } 256)\), and of course \(\displaystyle -79 \equiv 177\)
This always works...
Last edited: