2
$\begingroup$

I'm stuck with following problem and would need some help:

Express the following congruence system as a single congruence equation $$ x\equiv 3\pmod{7}\\x\equiv 9\pmod{13} $$ i.e. $$ x\equiv a\pmod{b} $$

With the Chinese remainder theorem I have found that

$$ x\equiv a\pmod{91}, $$

where $1\le a\le 91$. I know the answer too, $a=87$, i.e.

$$ x\equiv 87\pmod{91} $$

It can be solved either with intuition or testing all numbers from 1 to 91. However, I have to find solution to this algebraically, not intuitively, in which I have not been very successful. So, is there someone able to come up with the steps to the correct solution?

$\endgroup$
4
  • 2
    $\begingroup$ Have you learned about reciprocals in number theory? $\endgroup$
    – Trebor
    Sep 12 at 12:40
  • 1
    $\begingroup$ $\frac{p}{q}\Rightarrow \frac{q}{p}$? Yes, I have. $\endgroup$
    – Steve
    Sep 12 at 12:47
  • $\begingroup$ For instance, what's the reciprocal of 3 mod 7? The answer is 5. $\endgroup$
    – Trebor
    Sep 12 at 13:08
  • 1
    $\begingroup$ $x\equiv-4\bmod 7,13$, so $x\equiv-4\bmod 91$ $\endgroup$ Sep 13 at 14:05
2
$\begingroup$

You know that $x \equiv 3 \pmod{7}$, so $x=3+7n$ for some $n$. Plug that into the other congruence and solve:

$$3+7n \equiv 9 \pmod{13}$$

$$7n\equiv 6 \pmod{13}$$

$$n \equiv 14n \equiv 12 \equiv -1 \pmod{13}$$

So $n = -1 +13k$ for some $k$. Put that in the first equation:

$$x = 3 + 7(-1+13k) = -4 + 91k.$$

The last expression represents all solutions. Take $k=1$ and you get $87.$

$\endgroup$
2
$\begingroup$

Alternative approach that piggybacks on the intermediate result from B. Goddard's answer:

$x = 3 + 7n \equiv 9 \pmod{13}.$

Identify, either by trial and error, or the Euclidean Algorithm, that the reciprocal of $7 \pmod{13}$ is $(2)$.

That is $2 \times 7 \equiv 1 \pmod{13}.$

Therefore, $2x = 6 + [(2 \times 7) \times n] \equiv 6 + n \equiv (2 \times 9) = 18 \equiv 5 \pmod{13}.$

Therfore, the problem reduces to solving for $n$ where

$6 + n \equiv 5 \pmod{13} \implies n \equiv 12 \pmod{13}.$

Therefore, $x \equiv 3 + (7 \times 12) = 87 \pmod{7 \times 13}.$

$\endgroup$
1
$\begingroup$

$$9-3=6$$ and $$13\equiv 6\pmod 7$$ turn $$13z+9=7a+3$$ into $$6(z+1)=7a$$ which means it has a multiple of $$42=6\cdot 7$$ just $3$ below it. So it's either $45$ or $87$ . And checking modulo $13$ shows it's $87$

$\endgroup$
2
  • $\begingroup$ Needs mathjax editing. $\endgroup$ Sep 12 at 22:55
  • $\begingroup$ Thanks @user2661923 stupidly missed a single dollar sign matchup $\endgroup$ Sep 12 at 22:56

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.