- #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$ ?
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$ ?