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

  • MHB
  • Thread starter evinda
  • Start date
In summary: 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$....
  • #1
evinda
Gold Member
MHB
3,836
0
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$ ? :confused:
 
Mathematics news on Phys.org
  • #2
Hey! :eek:

evinda said:
$$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$ ? :confused:

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.
magicoups.gif


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

Attachments

  • magic.gif
    magic.gif
    1.5 KB · Views: 75
  • #3
I like Serena said:
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)
 
  • #4
evinda said:
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.
 
  • #5
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.
 
  • #6
I like Serena said:
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? :confused:

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)
 
  • #7
evinda said:
Why isn't $x_0$ required to be a solution? :confused:

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)
 
  • #8
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.
 
  • #9
mathbalarka said:
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.
 
  • #10
I like Serena said:
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)
 
  • #11
The problem asked for *positive* integers, but in this case $x_0$ is not positive. It can only be used as a seed.
 
  • #12
mathbalarka said:
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)
 
  • #13
No, me and ILS were referring to the seed $(x_0, y_0) = (30, -10)$.
 
  • #14
mathbalarka said:
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) :confused:
 
  • #15
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.
 
  • #16
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$ ? :confused:
 
  • #17
evinda said:
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$ ? :confused:

Yes. (Nod)
 
  • #18
I like Serena said:
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)
 
  • #19
evinda said:
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)
 
  • #20
I like Serena said:
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)
 
  • #21
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.
 
  • #22
mathbalarka said:
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)
 

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

What is the purpose of solving a congruence?

The purpose of solving a congruence is to find the values of the unknown variable(s) that satisfy the given congruence equation. This can help in solving various problems in number theory, cryptography, and other areas of mathematics.

Why do we use congruences instead of equations?

Congruences are used instead of equations because they provide a more concise and efficient way of expressing relationships between numbers. They also have specific properties and properties of arithmetic that make them useful in solving certain types of problems.

What are the main methods for solving congruences?

The main methods for solving congruences are the division method, the substitution method, and the Chinese Remainder Theorem. These methods involve manipulating the congruence equation in different ways to find the solutions.

How can solving congruences be applied in real life?

Solving congruences can be applied in real life in various areas such as cryptography, computer science, and engineering. It can also be used to solve problems involving modular arithmetic, which has applications in fields such as music, art, and game theory.

What are some common mistakes when solving congruences?

Some common mistakes when solving congruences include forgetting to check for extraneous solutions, not considering all possible solutions, and making errors in the calculations. It is important to carefully follow the steps and check the solutions to avoid these mistakes.

Similar threads

Replies
2
Views
4K
Replies
3
Views
2K
Replies
6
Views
906
Replies
1
Views
1K
Replies
4
Views
2K
Replies
2
Views
933
Back
Top