- #1

evinda

Gold Member

MHB

- 3,836

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