Solve $22t \equiv 9 \pmod{7}$

Question

I am trying to solve a modular arithmetic system and I got to the point where I have to solve $22t \equiv 9 \pmod{7}$ for $t$. I researched on the internet and found that there are many ways to solve this, such as using linear diophantine equations, the euclidean algorithm or using inverses.

Can someone show me, using which ever method they choose how to solve for $t$.

$22\equiv 1\pmod{7}$. – André Nicolas Feb 12 '16 at 02:47 — André Nicolas, Feb 12 '16 at 02:47
And $9 \equiv 2 \pmod{7}$. – N. F. Taussig Feb 12 '16 at 02:51 — N. F. Taussig, Feb 12 '16 at 02:51

score 1 · Accepted Answer · answered Feb 12 '16 at 02:58

The way it works is that you can subtract as many $7$'s from the numbers as you want. So subtract three $7$'s from the $21$ and it simply becomes $1$. And subtract one $7$ from the $9$ and it becomes $2$. So this really just says $t\equiv 2\pmod 7$. And there's your solution. This was a particularly easy linear equation to solve since you didn't need to find the inverse of the coefficient of $t$.

score 0 · Answer 2 · answered Feb 12 '16 at 03:46

Without learning more theory, the basic identity here is that $$ a \equiv b\; (mod\; c)$$ if and only if $$ \; c\; | \;a - b $$

So for $22t\; \equiv 9\;(mod \;7)$, we see $7\;|\;22t - 9$, which means we can rewrite this as a linear combination (where the Euclidean Algorithm would come into play) as $$22t - 9 = 7n$$ for some $n \in \mathbb Z$

But this is straightforward enough that we can just quickly look for the smallest smallest $t \in \mathbb N$ such that some $n \in \mathbb Z$ gives us a difference of 9. And we can quickly see that there is no such combination for $t=1$, and that the next smallest possibility $t=2$ and $n=-5$ works.

So $t=2$, hence $t \equiv 2\;(mod\;7)$

score 0 · Answer 3 · edited Apr 13 '17 at 12:21

A solution t = 2 - 7y where y is from the set of Integers.

Notes (Chionglo, 2015)

A linear system of congruencies is equivalent to a linear system of equations where the coefficients and variables are elements of the set of Integers (Z). It is possible to solve a linear system of equations in Z by symbolic manipulation using the “generally accepted definitions, laws and theorems” for the set of Integers. The method of substitution is used in two ways in the manipulations. For the first way, substitution is used to add parameter variables and corresponding equations. For the second way, substitution is used to eliminate variables from existing equations. By judiciously applying the method of substitution in these two ways, a basis can be found where every original variable is expressed in terms of parameter variables.
A guiding principle in applying the method of substitution is to express the original variables in terms of parameter variables.
Based on the symbolic manipulations, it is possible to work with an augmented matrix instead of directly manipulating the symbols; in other words, perform matrix operations on the augmented matrix. This reduces the amount work and the time needed to find a basis.

References

Chionglo, J. F. (2016). A Reply to "Solve 22t == 9 (mod 7) at Mathematics Stack Exchange". Available at http://www.aespen.ca/AEnswers/1455258289.pdf.

Chionglo, J. F. (2015). A Reply to “Find Solutions to Linear [Congruencies]”. Available at http://www.aespen.ca/AEnswers/Reply$1447217299.pdf.

“Solve “ (2016). Mathematics Stack Exchange. Retrieved on Feb. 11, 2016 at Solve $22t \equiv 9 \pmod{7}$.

Solve $22t \equiv 9 \pmod{7}$

3 Answers3

Notes (Chionglo, 2015)

References