System of congruences?

Question

Find all the integers $x\in \mathbb{Z}$ that satisfy the following system of equations (that is, the solution has to satisfy both equations simultaneously):

$2x\equiv 1 (mod7)$

$x^{2}\equiv 1 (mod 5)$

Any help is appreciated

Answer 1

By iterating over $\mathbb{Z}_{35}$, we see that the solutions are of the form $x\equiv 4 \text{ (mod 35)}$ or $x\equiv 11 \text{ (mod 35)}$.

Answer 2

$x^2 \equiv 1 \pmod 5 \to 5|x^2 - 1 = (x - 1)(x + 1)$. Since $5$ is a prime, either $5|x - 1$ or $5|x + 1$.

Case 1: $5|x - 1$. So: $x - 1 = 5k \to x = 5k + 1$, and substituting this value of $k$ into the first equation: $2(5k + 1) = 10k + 2 \equiv 1 \pmod 7$. This means:

$10k + 2 - 1 = 7n \to 10k + 1 = 7n \to k = \dfrac{7n - 1}{10} = n - \dfrac{3n + 1}{10}$. At this point, we require that: $3n + 1 = 10p \to n = \dfrac{10p - 1}{3} = 3p + \dfrac{p - 1}{3}$. Thus: $p - 1 = 3r$, or $p = 3r + 1 \to n = \dfrac{10(3r + 1) - 1}{3} = \dfrac{30r + 9}{3} = 10r + 3 \to k = \dfrac{7n - 1}{10} = \dfrac{7(10r + 3) - 1}{10} = \dfrac{70r + 20}{10} = 7r + 2 \to x = 5k + 1 = 5(7r + 2) + 1 = 35r + 11$, $r \in \mathbb{Z}$

Case 2: $5|x + 1$. You can use my work in case 1 and see how far you can go.

Answer 3

The first thing we want to do is solve for x in both equivalences. $2$ is easy to find an inverse for. Multiply both sides of the first equivalence by $4$ to yield

$$x\equiv4\pmod7$$

For the second, subtract $1$ from both sides to get

$$x^2-1=(x+1)(x-1)\equiv0\pmod5$$

In other words, $5|(x+1)(x-1)$. Since $5$ is prime, it must divide one of the $2$ factors (it can't divide both). This leads to

$$x\equiv 1\text{ or }4\pmod5$$.

So we have $2$ cases:

$$x\equiv4\pmod7,x\equiv4\pmod5$$ or $$x\equiv4\pmod7,x\equiv1\pmod5$$

Since $5$ and $7$ are coprime, each set of equivalences guarantees a unique solution to

$$x\equiv a\pmod{35}$$

The first case is easy. We have $x-4$ is a multiple of both $5$ and $7$, so $x\equiv4\pmod{35}$. The second case is a bit trickier, but given the size of the numbers, trial and error is probably best. You only need test values with a last digit of $1$ or $6$ and the solution $11=7+4$ isn't too hard to find.