Log In Start studying!

Select your language

Suggested languages for you:

Americas

English (US)

Europe

Q11E

Expert-verified

Abstract Algebra: An Introduction

Found in: Page 448

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
11.
$x \equiv 2 (m o d 5) x \equiv 0 (m o d 6) x \equiv 3 (m o d 7)$

The system of congruence is obtained as $x \equiv - 18 (m o d 210)$ .

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Conceptual Introduction

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

Then the system,

role="math" localid="1659451269093" $x \equiv a_{1} ({modm}_{1}) x \equiv a_{2} ({modm}_{2}) x \equiv a_{3} ({modm}_{3}) . . . x \equiv a_{r} (m o d m_{r})$

has a solution.

Step 2: Evaluating the system of congruence for x≡2(mod5) and x≡(mod6)

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

$x \equiv a (m o d m) \dots \dots (1) x \equiv b (m o d n) \dots \dots (2)$

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

$t = b m u + a n v$ …… (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 2 (m o d 5)$ …… (5)

And,

$x \equiv 0 (m o d 6)$ ……. (6)

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

m = 5 , n = 6 , a = 2 and b = 0

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

5u +6v = 1

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

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

$\begin{array}{rcl} t & = & 0 \times 5 \times (- 1) + 2 \times 6 \times 1 \\ = & 12 \end{array}$

So the required solution is given by,

$\begin{array}{rcl} x & \equiv & 12 (m o d 6 \times 5) \\ \equiv & 12 (m o d 30) \end{array}$ ...... (7)

Step 3: Evaluating the system of congruence for x≡2(mod7)

Now the third system of congruence is given by,

$x \equiv 3 (m o d 7)$ ...... (8)

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

$m = 30, n = 7, a = 12 a n d b = 3$

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

$30 u + 7 v = 1$

From the heat and trial method, above equation holds true for u = -3 and v = 13

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{array}{rcl} t & = & b m u + a n \\ = & 3 \times 30 \times (- 3) + 12 \times 7 \times 13 \\ = & 822 \end{array}$ ........ (9)

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

role="math" localid="1659452713423" $\begin{array}{rcl} x & \equiv & 822 (m o d 30 \times 7) \\ \equiv & 822 (m o d 210) \\ \equiv & - 18 (m o d 210) \end{array}$

Therefore the final solution is $x \begin{array}{rcl} \equiv \end{array} \begin{array}{rcl} - \end{array} \begin{array}{rcl} 18 \end{array} \begin{array}{rcl} (m o d 210) \end{array}$ .

Most popular questions for Math Textbooks

Question:- If (a,n) = 1and s,t are solution of $ax \equiv b(modn)$ prove that $s \equiv t (modn)$ [Hint show that t and use theorem ]

Question: - If $(m,n) \neq 1$ show that Z_mn is not isomorphic to $Z_{m} \times Z_{n}$ [Hint: if (m,n) = d then $\frac{mn}{d}$ is an integer (why).If there were an isomorphism,() then $1 \in Z_{mn}$ would be mapped to $(1, 1) \in Z_{m} \times Z_{n}$ . Reach a contradiction by showing that $\frac{mn}{d} .1 \neq 0$ in $Z_{mn}$ ,show that $\frac{mn}{d} . (1, 1) = (0, 0)$ in $Z_{m} \times Z_{n}$ .

Question: If (m,n) =d , prove that $x \equiv a(mod m)$ and $x \equiv b (mod m)$ has a solution if and only if $a \equiv b(mod d)$ .

If $s$ , role="math" localid="1659435566500" $t$ are solution of the system in exercise $19$ , prove that $s \equiv t (mod r)$ , where $r$ is the least common multiple of $m$ and $n$ .

Let $f : ℤ \to ℤ_{3} \times ℤ_{4} \times ℤ_{5}$ be given by $f (t) = ({[t]}_{3}, {[t]}_{4}, {[t]}_{5})$ ,where ${[t]}_{n}$ is the congruence class of $t$ in $ℤ_{n}$ . The function $f$ may be thought of as representing t as an element of role="math" localid="1658833286608" $ℤ_{3} \times ℤ_{4} \times ℤ_{5}$ by taking its least residues.

If $0 \leq r, s < 60$ , prove thatif and only if $r = s$ . [Hint: Theorem 14.2.]
Give an example to show that if $r$ or $s$ is greater than 60, then part (a) may be false.

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