MHB Why Do We Solve the Congruence \(7x \equiv 1 \pmod{11}\) to Find Solutions?

[evinda]

Hello! (Wave)

I am looking at the following exercise:

Find two positive integers, multiple of $7$ and $11$ respectively, of which the sum is equal to $100$.

According to my notes:

The numbers are of the form $7x$ and $11y$.

$$7x+11y=100$$

$$(7,11)=1 \mid 100, \text{ so the equation has infinite solutions.}$$

We solve the congruence:

$$7x \equiv 1 \pmod {11}$$

We find $x \equiv 8 \pmod {11}$

$$x_0=8, y_0=4$$

The set of solutions in $\mathbb{Z} $ is:

$$\{ x_m=x_0+ \frac{b}{d}m , y_m=y_0-\frac{a}{d}m, m \in \mathbb{Z}\}$$

where $d=gcd(a,b)$

So:

$$x_m=8+11m , \ \ \ \ y_m=4-7m, m \in \mathbb{Z}$$

$$x_m>0 \text{ and } y_m>0 \Rightarrow m=0$$

Therefore, the only solution is $(8,4)$.

Could you explain me why we solve the congruence $7x \equiv 1 \pmod{11}$, in order to find a $x_0$ ?

 

[I like Serena]

Hey!

$$7x+11y=100$$

We solve the congruence:

$$7x \equiv 1 \pmod {11}$$

Could you explain me why we solve the congruence $7x \equiv 1 \pmod{11}$, in order to find a $x_0$ ?

It's a trick! View attachment 3282

A trick to simplify the equation to something that is easier to solve... by effectively eliminating $y$.
We can do so by taking the equation modulo $11$.
When we do so, $y$ vanishes.

$$7x+11y=100
\Rightarrow 7x+11y \equiv 100 \pmod{11}
\Rightarrow 7x \equiv 1 \pmod{11}$$

 

[evinda]

It's a trick! View attachment 3282

A trick to simplify the equation to something that is easier to solve... by effectively eliminating $y$.
We can do so by taking the equation modulo $11$.
When we do so, $y$ vanishes.

$$7x+11y=100
\Rightarrow 7x+11y \equiv 100 \pmod{11}
\Rightarrow 7x \equiv 1 \pmod{11}$$

Nice! (Yes)

Solving the congruence $7x \equiv 1 \pmod{11}$, we find $x \equiv 8 \pmod {11}$, so $x=8+11k, k \in \mathbb{Z}$ is a solution of the equation $7x+11y=100$, right?

Can we then pick whichever $k$ we want and replace this at $x=8+11k$, to find a $x_0$? Could we also pick, for example, $k=1$ ? (Thinking)

 

[I like Serena]

Nice! (Yes)

Solving the congruence $7x \equiv 1 \pmod{11}$, we find $x \equiv 8 \pmod {11}$, so $x=8+11k, k \in \mathbb{Z}$ is a solution of the equation $7x+11y=100$, right?

Can we then pick whichever $k$ we want and replace this at $x=8+11k$, to find a $x_0$? Could we also pick, for example, $k=1$ ? (Thinking)

Yes, since $x_0$ is not required to be a solution.
It's only an arbitrary starting point for all possible solutions.

 

[mathbalarka]

Darn, can't believe I missed a number theory question.

The general trick to solve these kind of problems are to consider them modulo something to vanish one of the terms . There are several way to do this : take your equation $7x + 11y = 100$ which is just $11(x + y) - 4x = 100$ and modulo $11$ this is just $-4x = 99 + 1 = 1$. Thus inverting $4$ modulo $11$, one gets $x = -4^{-1} = -3 = 8$.

Can we then pick whichever $k$ we want and replace this at $x=8+11k$, to find a $x_0$? Could we also pick, for example, $k=1$ ?

What you need to understand is that solutions to these linear dioph. equations will never be AN integer. It'll be either a null set or an infinite set of ordered pairs of integers. And modulo notations are not actually quite "numbers" either. For example, that $8 \pmod{11}$ thingy is really the set (NOT a number) $\{8 + 11k : k \in \Bbb Z\}$. If you're asked to show only two solutions, just pick something up from the set.

 

[evinda]

Yes, since $x_0$ is not required to be a solution.
It's only an arbitrary starting point for all possible solutions.

Why isn't $x_0$ required to be a solution?

According to my notes:

The general diophantine equation of first degree is $aX+bY=c , a,b,c \in \mathbb{Z}$.
This equation has a solution $\Leftrightarrow$ $(a,b) \mid c$.
If it has a solution $(x_0,y_0) \in \mathbb{Z}^2$, then it has infinite solutions.
The set of solutions is this:

$$\{ (x_m,y_m) | x_m=x_0+\frac{b}{d}m , \ \ \ y_m=y_0-\frac{a}{d}m \}$$
(Thinking) (Thinking) (Thinking)

 

[I like Serena]

Why isn't $x_0$ required to be a solution?

According to my notes:

The general diophantine equation of first degree is $aX+bY=c , a,b,c \in \mathbb{Z}$.
This equation has a solution $\Leftrightarrow$ $(a,b) \mid c$.
If it has a solution $(x_0,y_0) \in \mathbb{Z}^2$, then it has infinite solutions.
The set of solutions is this:

$$\{ (x_m,y_m) | x_m=x_0+\frac{b}{d}m , \ \ \ y_m=y_0-\frac{a}{d}m \}$$
(Thinking) (Thinking) (Thinking)

Oh yes.
Sorry. (Wasntme)
You are right, $x_0$ does have to be a solution.

Still, you can't pick just any $k$.
You need to search for a $k$ such that you find an $x_0$ that satisfies the original equation.

That is because we have a logic chain like $A \Rightarrow B \Rightarrow C$.
So a solution of $C$ is not necessarily a solution of $A$.
But a solution of $A$ will be contained in $C$. (Smile)

 

[mathbalarka]

I don't understand why I can't pick any $k$, ILS. evinda already found $x = 8 \pmod{11}$ so $x = 8 + 11k$ is a class of solution that satisfies the equation. I can, for example, pick up $k = 2$ so that $x_0 = 8 + 22 = 30$ and the corresponding $y_0$ is then found as $11y_0 = 100 - 30 \cdot 7 = 100 - 210 = -110$ and hence $y_0 = -10$. Clearly $(x_0, y_0) = (30, -10)$ is another seed.

 

[I like Serena]

I don't understand why I can't pick any $k$, ILS. evinda already found $x = 8 \pmod{11}$ so $x = 8 + 11k$ is a class of solution that satisfies the equation. I can, for example, pick up $k = 2$ so that $x_0 = 8 + 22 = 30$ and the corresponding $y_0$ is then found as $11y_0 = 100 - 30 \cdot 7 = 100 - 210 = -110$ and hence $y_0 = -10$. Clearly $(x_0, y_0) = (30, -10)$ is another seed.

That's because I'm having a bad day. (Wink)

So yes, we can pick any $k$ to set $x_0$, which will be a part of the solution of the more general problem in $\mathbb Z$.
This $x_0$ is not necessarily a solution of the actual problem statement though.

 

[evinda]

That's because I'm having a bad day. (Wink)

So yes, we can pick any $k$ to set $x_0$, which will be a part of the solution of the more general problem in $\mathbb Z$.
This $x_0$ is not necessarily a solution of the actual problem statement though.

Why isn't this $x_0$ necessarily a solution of the actual problem statement? (Worried)

 

[mathbalarka]

The problem asked for *positive* integers, but in this case $x_0$ is not positive. It can only be used as a seed.

 

[evinda]

The problem asked for *positive* integers, but in this case $x_0$ is not positive. It can only be used as a seed.

Isn't it equal to $8$? (Sweating)

 

[mathbalarka]

No, me and ILS were referring to the seed $(x_0, y_0) = (30, -10)$.

 

[evinda]

No, me and ILS were referring to the seed $(x_0, y_0) = (30, -10)$.

So, can we only pick as $x_0$ the solution we found solving the congruence $7x \equiv 1 \pmod {11}$ for $k=0$, since replacing it at the diophantine equation $7x+11y$, we found a positive $y_0$ ? (Thinking)

 

[mathbalarka]

I am not sure if I understand you, but you *can* invert $7x$ modulo $11$ to find $x_0$ and substitute that back into find the corresponding $y_0$ such that $(x_0, y_0)$ works as a seed of the solutions when substituted in the general formula for linear $\Bbb Z^2$-diophantine equations.

 

[evinda]

So, having an equality $ax+by=c$, after finding a $x_0$, by solving the congruence $ax \equiv c \pmod b$ , can we always find a $ y_0 $, so that $(x_0,y_0) $ is a solution of $ ax+by=c$ ?

 

[I like Serena]

So, having an equality $ax+by=c$, after finding a $x_0$, by solving the congruence $ax \equiv c \pmod b$ , can we always find a $ y_0 $, so that $(x_0,y_0) $ is a solution of $ ax+by=c$ ?

Yes. (Nod)

 

[evinda]

Yes. (Nod)

A ok.. And, in our case we take the first $x_0>0$ we found, since $x_0$ and $y_0>0$, right ?
But, if we would find a $x_0$ such that $y_0<0$ would we take the next $x_0$, that corresponds to an other value of $k$, for which $y_0>0$ ? Or am I wrong? (Thinking)

 

[I like Serena]

A ok.. And, in our case we take the first $x_0>0$ we found, since $x_0$ and $y_0>0$, right ?
But, if we would find a $x_0$ such that $y_0<0$ would we take the next $x_0$, that corresponds to an other value of $k$, for which $y_0>0$ ? Or am I wrong? (Thinking)

In the first stage of the solution, we pick an $x_0$ and $y_0$ that satisfies the equation in $\mathbb Z$. At this stage it is not relevant whether they are positive or not.
We can construct all possible solutions from them in $\mathbb Z$.

In the next stage of the solution, we try to figure out which of these solutions have both $x$ and $y$ positive. (Nerd)

 

[evinda]

In the first stage of the solution, we pick an $x_0$ and $y_0$ that satisfies the equation in $\mathbb Z$. At this stage it is not relevant whether they are positive or not.
We can construct all possible solutions from them in $\mathbb Z$.

In the next stage of the solution, we try to figure out which of these solutions have both $x$ and $y$ positive. (Nerd)

So, taking $(x_0,y_0)=(30,-10)$, we have:

$$x=30+11m, y=-10-7m$$

$$x>0 \Rightarrow 30+11m>0$$

$$y>0 \Rightarrow -10-7m>0 $$

$$\Rightarrow m=-2$$

Therefore, the only solution is:

$$(30+11 \cdot (-2),-10-7 \cdot (-2) )=(8,4)$$

So, no matter which $(x_0,y_0)$, that satisfies the initial equation, we take, we will get the same result, right? (Smile)

Thank you very much! (Happy)

 

[mathbalarka]

Yes, the essence of the formula you produced for linear diophantine equations is that given at least one solution $(x_0, y_0)$ it'd return all of the solutions back. So picking up any (positive or negative) $(x_0, y_0)$ pair, it doesn't really matter what the signs are as it'd generate all the other solutions.

After getting the solutions, you can impose some restrictions like positivity and inspect what happens to the pairs then.

 

[evinda]

Yes, the essence of the formula you produced for linear diophantine equations is that given at least one solution $(x_0, y_0)$ it'd return all of the solutions back. So picking up any (positive or negative) $(x_0, y_0)$ pair, it doesn't really matter what the signs are as it'd generate all the other solutions.

After getting the solutions, you can impose some restrictions like positivity and inspect what happens to the pairs then.

Nice, thanks a lot! (Smile)