0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Rewrite as $x\equiv 1\pmod{7}$, $x\equiv \pm 1\pmod{5}$. $\endgroup$ – André Nicolas May 11 '14 at 21:28
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the help ... however if I have in the second equation something like $x^{2}\equiv 2 (mod 5)$, then I don´t know what to do because I have $x^{2}-2 = 0$ and so I obtain a square root of 2 $\endgroup$ – user132226 May 11 '14 at 22:33
  • $\begingroup$ @user132226 That complicates things greatly. The answer, though, is there would be no solution. $x^2\equiv2\pmod5$ has no solution. $\endgroup$ – Mike May 11 '14 at 22:48
0
$\begingroup$

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)}$.

$\endgroup$
  • $\begingroup$ What is iteration ?? Is it some sort of trial and error ?? And why we iterate over $\mathbb{Z}_{35}$ ?? Is it because 35 = 7 x 5 ?? $\endgroup$ – user132226 May 11 '14 at 21:39
  • $\begingroup$ Yes, iterating over $\mathbb{Z}_{35}$ means testing each $x=1,2,\dots,34$. We only test the first 35 values because $\text{lcm}(5,7) = 35$ -- then it cycles. $\endgroup$ – fahrbach May 11 '14 at 21:44
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.