Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is excercise 1 in George E. Andrews number theory. page 51. How am i supposed to solve this? Thanks very much in advance. I used the cancellation law to get isolate the x. But I don’t know what to do next.

$5x\equiv 4 \pmod 3$

$7x\equiv 6 \pmod 5$

$9x\equiv 8 \pmod 7$

share|improve this question
    
Were these $3$ separate problems or related to the Chinese Remainder Theorem to find an $x$ that satisfies them simultaneously? –  Amzoti Dec 28 '12 at 19:41
    
I havent seen chinese remainder theorem yet –  Jorge Fernández Dec 28 '12 at 19:41
    
Then Fermat's Little Theorem should suffice. –  Amzoti Dec 28 '12 at 19:42

3 Answers 3

up vote 4 down vote accepted

The numbers are very special! Our system is equivalent to $2x\equiv 1$ modulo $3$, $5$, $7$, or equivalently $2x\equiv 1\pmod{105}$.

To solve $2x\equiv 1\pmod{105}$, rewrite as $2x\equiv 106\pmod{105}$. This has solution $x\equiv 53\pmod{105}$.

share|improve this answer
    
+1. Neat ${}{}$ –  user17762 Dec 28 '12 at 19:44

Observe that in each case, $ax\equiv1\equiv a^{p-1}\pmod p$

So, $x\equiv a^{p-2}\pmod p$

share|improve this answer
    
Are you using little Fermat? –  Jorge Fernández Dec 28 '12 at 19:39
    
@Khromonkey,exactly. –  lab bhattacharjee Dec 28 '12 at 19:40
    
How can i find an x such that $x\equiv a^p-2$ for p=3,5 and 7 simultaneously? –  Jorge Fernández Dec 28 '12 at 19:43
    
@Khromonkey, for example, $p=3,a=5, x\equiv 5^{3-2}\equiv\pmod 3\equiv 2$, then apply CRT –  lab bhattacharjee Dec 28 '12 at 19:45
    
i dont know how to use chinese remainder theorem but ill +1 anyways because ill read it once I read about it. –  Jorge Fernández Dec 28 '12 at 19:48

$$5 x \equiv 1 \pmod 3 \implies x \equiv 2 \pmod 3$$ $$7 x \equiv 1 \pmod 5 \implies x \equiv 3 \pmod 5$$ $$9 x \equiv 1 \pmod 7 \implies x \equiv 4 \pmod 7$$ $$x \equiv 2 \pmod 3 \text{ and }x \equiv 3 \pmod 5 \implies x \equiv a \pmod{15}$$ Since $x \equiv 2 \pmod 3$, we have $a \in \{2,5,8,11,14\}$. Since $x$ is also $3 \pmod 5$, we get that $$x \equiv 8 \pmod {15}$$

$$x \equiv 8 \pmod {15} \text{ and }x \equiv 4 \pmod 7 \implies x \equiv b \pmod{105}$$ Since $x \equiv 8 \pmod 15$, we have $b \in \{8,23,38,53,68,83,98\}$. Since $x$ is also $4 \pmod 7$, we get that $$x \equiv 53 \pmod {105}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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