Log In Start studying!

Select your language

Suggested languages for you:

Americas

English (US)

Europe

Q12E

Expert-verified

Abstract Algebra: An Introduction

Found in: Page 449

Book edition 3rd

Author(s) Thomas W Hungerford, David Leep

Pages 608 pages

ISBN 9781111569624

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later

Short Answer

In exercise 8-13, solve the system of congruences
12.
$\begin{array}{l} x \equiv 1(mod5) \\ x \equiv 3(mod6) \\ x \equiv 5(mod11) \\ x \equiv 10(mod13) \end{array}$

The system of congruence is obtained as $x \equiv 621 (\mod 4290)$ .

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Conceptual Introduction

Let $m_{1}, m_{2} . ... m_{f}$ be pair wise relatively prime positive integers, (it means that $(m_{i}, m_{j}) = 1$ whenever $i \neq j$ ) . Assume that the $a_{1}, a_{2} . ...., a_{r}$ , are any integers.

Then the system,

$\begin{array}{l} x \equiv a_{1} (m o d m_{1}) \\ x \equiv a_{2} (m o d m_{2}) \\ x \equiv a_{3} (m o d m_{3}) \\ . \\ . \\ . \\ x \equiv a_{r} (m o d m_{r}) \end{array}$

has a solution.

Evaluating the system of congruences for x≡1(mod 5) and x≡3(mod 6) .

Assume that the numbers m and n are relatively prime integers. Then the following system of congruence equations has a solution.

$x \equiv a (modm)$ …… (1)

$x \equiv b (\mod n)$ …… (2)

Now from the above two equation solution can be obtained as,

$t = bmu + anv$ …… (3)

Here the numbers u and v are found such that the following equation is satisfied.

$mu + nv = 1$ …… (4)

Now the given congruence equations are:

$x \equiv 1 (\mod 5)$ …… (5)

And,

$x \equiv 3 (\mod 6)$ ……. (6)

Compare the equations (5) and (6) with (1) and (2) to obtain the following values,

$m = 5$ , $n = 6$ , $a = 1$ and data-custom-editor="chemistry" $b = 3$

Now find out the values of and such that the equation (4) is satisfied.

$5 u + 6 v = 1$

Above equation will get satisfied with the values $u = 1$ and $v = - 1$

Now substitute 3 for b , 5 for m , -1 for u , 1 for a , 6 for n and 1 for v into the equation (3)

$\begin{matrix} t = 3 \times 5 \times (- 1) + 1 \times 6 \times 1 \\ = - 9 \end{matrix}$

So the required solution is given by,

$\begin{matrix} x \equiv - 9 (\mod 6 \times 5) \\ \equiv - 9 (\mod 30) \\ \equiv 21 (\mod 30) \end{matrix}$ ...... (7)

Evaluating the system of congruence for x≡5(mod 11)

Now the third system of congruence is given by,

$x \equiv 5 (\mod 11)$ ...... (8)

Again compare the equations (7) and (8) with (1) and (2) to obtain the following values,

$m = 30$ , $n = 11$ , $a = 21$ and $b = 5$

Substitute 30 for m and 11 for n into the equation (4), and again find the values of u and v such that the equation (4) is satisfied.

$30 u + 11 v = 1$

From the heat and trial method, above equation holds true for and

Now substitute 3 for b , 30 for m , -3 for u , 12 for a , 7 for n and 13 for v into the equation (3)

$\begin{matrix} t = b m u + a n v \\ = 5 \times 30 \times (- 4) + 21 \times 11 \times 11 \\ = 1941 \end{matrix}$ ........ (9)

Now from the equation (7), (8) and (9), the required solution can be calculated,

$\begin{matrix} x \equiv 1941 (\mod 30 \times 11) \\ \equiv 822 (\mod 330) \\ \equiv - 39 (\mod 330) \end{matrix}$ ...... (10)

Evaluating the system of congruence for x≡10(mod 13)

Now the fourth congruence equation is given by,

$x \equiv 10 (\mod 13)$ ...... (11)

Now again compare the equation (10) and (11) with equation (1) and (2) to obtain the following values,

$m = 330$ , $n = 13$ , $a = - 39$ and $b = 10$

Substitute 330 for m and 13 for n into the equation (4)

$330 u + 13 v = 1$

From the heat and trial method $u = 8$ and $v = - 203$ holds true for the above equation,

Now substitute 10 for b , 330 for m , 8 for u , -39 for a , 13 for n and -203 for v into the equation (3)

$\begin{matrix} t = b m u + a n v \\ = 10 \times 330 \times 8 + (- 39) \times 13 \times (- 203) \\ = 129321 \end{matrix}$ ....... (12)

Now from the equation (10), (11) and (12), the required solution of the congruence is,

$\begin{matrix} x \equiv 129321 (\mod 330 \times 13) \\ \equiv 129321 (\mod 4290) \\ \equiv 621 (\mod 4290) \end{matrix}$

Therefore the system of congruence is obtained as $x \equiv 621 (\mod 4290)$ .

Most popular questions for Math Textbooks

Question: -If $(m, n) = 1$ and $\frac{m}{d}, \frac{n}{d}$ , prove that [Hint: - If $d = mk$ then $\frac{n}{mk}$ use theorem ]

In exercise 8-13, solve the system of congruences

11.

$x \equiv 2 (m o d 5) x \equiv 0 (m o d 6) x \equiv 3 (m o d 7)$

If I and J are ideals in a ring R and , $a \in l, b \in l$ show that $ab \in l \cap J$

Show that $6 x + 5 \equiv 7 (\mod 3)$ has no solutions. [Hint: Exercise 2]

In exercise 8-13, solve the system of congruences

$x \equiv 5(mod6) x \equiv 7(mod11)$

Want to see more solutions like these?

Sign up for free to discover our expert answers

Get Started - It’s free

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free