# How to find all solutions of ## 3x-7y\equiv 11\pmod {13} ##?

• Math100
In summary: You can view this as a discrete straight. In the same way, you can view the whole plane as a discrete plane. You even can view the whole space as a discrete space - and then you are in the realm of number theory.
Math100
Homework Statement
Find all solutions of the linear congruence ## 3x-7y\equiv 11\pmod {13} ##.
Relevant Equations
None.
Consider the linear congruence ## 3x-7y\equiv 11\pmod {13} ##.
Then ## 3x\equiv 11+7y\pmod {13} ##.
Note that ## gcd(3, 13)=1 ## and ## 1\mid 11 ##.
This means ## y\in\ {0, 1,..., 12} ##.

And now I'm stuck. The book's answer shows ## x\equiv 11+t\pmod {13}, y\equiv 5+6t\pmod {13} ##. But based on my previous work shown above, how should I get to the correct answer for this problem?

I'm not sure why they would write the answer in that manner. I'd start with (you can fill in some blanks)
##3x - 7y \equiv 11##

##3x \equiv 11 + 7y##

Multiply both sides by ##3^{-1}## to get x. Then you have
##x \equiv 8 + 11y##

Personally I'd leave it there, but if you like set ##x \equiv t##. Then solve ## t \equiv 8 + 11y## for y and you get ##y \equiv 6 t+ 2##.

I'll leave it to you to figure out how to get ##x = 11 + t## and ##y \equiv 5 + 6t## from there.

If you need more help, show us what you've got and we'll take it from there.

-Dan

fresh_42
Let's forget about the theorems for a moment.

We have ##3x-7y\equiv 11\pmod{13}## and all numbers here are coprime, so they all have inverses modulo ##13.## However, we have two variables but only one equation. It is now the same calculation which you use to solve linear equation systems. Only that we do not have rational numbers, but ##\{0,1,2,\ldots,12\}## instead.

Let's solve ##3a\equiv 1\pmod{13}.## We have ##3\cdot (-4)\equiv -12 \equiv 1 \pmod{13}## so ##a=3^{-1}\equiv -4\equiv 9\pmod{13}.## From that we get
\begin{align*}
3x-7y\equiv 11\pmod{13} &\Longrightarrow 9\cdot 3x-9\cdot 7y=99\pmod{13} \\
&\Longrightarrow 27x-63y\equiv 99\pmod{13}\\
&\Longrightarrow x-11y\equiv 8 \pmod{13} \\&\Longrightarrow x=11y+8
\end{align*}
##y## is arbitrary, a free parameter. So you could either choose any ##y## and calculate ##x## from it or the other way around.

topsquark
fresh_42 said:
Let's forget about the theorems for a moment.

We have ##3x-7y\equiv 11\pmod{13}## and all numbers here are coprime, so they all have inverses modulo ##13.## However, we have two variables but only one equation. It is now the same calculation which you use to solve linear equation systems. Only that we do not have rational numbers, but ##\{0,1,2,\ldots,12\}## instead.

Let's solve ##3a\equiv 1\pmod{13}.## We have ##3\cdot (-4)\equiv -12 \equiv 1 \pmod{13}## so ##a=3^{-1}\equiv -4\equiv 9\pmod{13}.## From that we get
\begin{align*}
3x-7y\equiv 11\pmod{13} &\Longrightarrow 9\cdot 3x-9\cdot 7y=99\pmod{13} \\
&\Longrightarrow 27x-63y\equiv 99\pmod{13}\\
&\Longrightarrow x-11y\equiv 8 \pmod{13} \\&\Longrightarrow x=11y+8
\end{align*}
##y## is arbitrary, a free parameter. So you could either choose any ##y## and calculate ##x## from it or the other way around.
Since ## y\in {0, 1,..., 12} ##, it follows that ## x=11(0)+8=0+8=8 ##. So ## x=8, y=0 ##. Then what should be the answer?

Math100 said:
Since ## y\in {0, 1,..., 12} ##, it follows that ## x=11(0)+8=0+8=8 ##. So ## x=8, y=0 ##. Then what should be the answer?
The answer is a set that has as many elements as there are solutions. Since ##y## can freely be chosen, there will be thirteen answers, for every value of ##y## one. You have noted ##(x,y)=(8,0).## The solution is either ##\{(x,y)=(11y+8,y)\pmod{13}\,|\,0\leq y \leq 12\}## or you list all thirteen: ##\{(8,0),(6,1),(4,2),\ldots\}.##

topsquark and Math100
fresh_42 said:
The answer is a set that has as many elements as there are solutions. Since ##y## can freely be chosen, there will be thirteen answers, for every value of ##y## one. You have noted ##(x,y)=(8,0).## The solution is either ##\{(x,y)=(11y+8,y)\pmod{13}\,|\,0\leq y \leq 12\}## or you list all thirteen: ##\{(8,0),(6,1),(4,2),\ldots\}.##
I do not think listing all thirteen pairs of sets is a good idea, but I do prefer the first solution you've provided.

Math100 said:
I do not think listing all thirteen pairs of sets is a good idea, but I do prefer the first solution you've provided.
The point that you should get here is, that the remainders of primes, here ##13,## form a field. Fields are structures where we can add, subtract, multiply and divide. We normally only consider the rational numbers, or the reals, maybe even the complex numbers. But ##\{0,1,2,\ldots,12\}## is a field, too. It has only thirteen elements, but it provides all calculation rules. Therefore ##3x-7y=11\pmod{13}## is the equation of a straight in a plane. The plane has only ##13^2=169## points, but who cares? The straight has ##13## points.

topsquark and Math100

## 1. What is the general method for finding all solutions of a congruence equation?

The general method for finding all solutions of a congruence equation is to first reduce the equation to its simplest form by using modular arithmetic. Then, systematically test values for the unknown variable until a solution is found.

## 2. How do I reduce a congruence equation to its simplest form?

To reduce a congruence equation to its simplest form, use the properties of modular arithmetic to eliminate any coefficients or constants on the unknown variable. This will leave the equation in the form of x ≡ a (mod m), where x is the unknown variable, a is a constant, and m is the modulus.

## 3. What is the modulus in a congruence equation?

The modulus in a congruence equation is the number that the unknown variable is being taken modulo of. It is represented by the "mod" symbol and is typically denoted as m. In the equation 3x ≡ 11 (mod 13), the modulus is 13.

## 4. How do I systematically test values for the unknown variable?

To systematically test values for the unknown variable, start by choosing a value for the unknown variable that satisfies the equation in its simplest form. Then, add or subtract the modulus until all possible solutions have been found. For example, in the equation 3x ≡ 11 (mod 13), start with x = 4, then add 13 to get x = 17, and subtract 13 to get x = -9.

## 5. Can a congruence equation have more than one solution?

Yes, a congruence equation can have more than one solution. In fact, there can be an infinite number of solutions depending on the modulus and the equation itself. However, it is important to note that there can also be cases where a congruence equation has no solutions.

• Precalculus Mathematics Homework Help
Replies
1
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
723
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
2K
• Precalculus Mathematics Homework Help
Replies
1
Views
978
• Precalculus Mathematics Homework Help
Replies
1
Views
979
• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
1K