Explanation Given information: x and y are integers. Formula used: i) Definition: Equivalence class: Let R be an equivalence relation on the non-empty set A . For each a ∈ A , the set [ a ] = { x ∈ A | x R a } is called the equivalence class containing a . ii) Definition: Congruence Modulo n Let n be a positive integer, n > 1 . For integers x and y , x is congruent to y modulo n , if and only if x − y is a multiple of n . We write x ≡ y ( mod n ) to indicate that x is congruent to y modulo n . iii) Definition: An integer d is a greatest common divisor of a and b if all these conditions are satisfied: 1. d is a positive integer. 2. d | a and d | b . 3. c | a and c | b imply c | d . Proof: Let x , y , a ∈ ℤ , such that x ∈ [ a ] and y ∈ [ a ] . x ∈ [ a ] implies that x ≡ a ( mod n ) and y ∈ [ a ] implies that y ≡ a ( mod n ) By transitivity and symmetry, x ≡ y ( mod n ) By using definition, x − y is multiple of n . Let x − y = n q for q ∈ ℤ . This implies y = x − n q and x = y + n q . Let d 1 = ( x , n ) and d 2 = ( y , n ) By using definition, d 1 | x and d 1 | n , then d 1 divides any linear combination of x and n

8th Edition

ISBN: 9780357671139

Author: Gilbert

Publisher: CENGAGE L

See similar textbooks

Videos

Question

Chapter 2.5, Problem 36E

To determine

To prove: If there is an equivalence class [a] modulo n, such that x∈[a] and y∈[a], then (x, n)=(y, n), where x and y are integers.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 2.5, Problem 35E

Chapter 2.5, Problem 37E

Students have asked these similar questions

Consider the following equation. log1/9' =6 Find the value of x. Round your answer to the nearest thousandth. x = ✓

Expanding a logarithmic expression: Problem type 3 Use the properties of logarithms to expand the following expression. 4(8+x)² log 5 ) Your answer should not have radicals or exponents. You may assume that all variables are positive. log 4(8 + X 5 -x)²

Use the properties of logarithms to expand the following expression. log 6(x+5)² 3/24 Your answer should not have radicals or exponents. You may assume that all variables are positive. log 6(x + 3 I 4 5)² log X

Chapter 2 Solutions

ELEMENTS OF MODERN ALGEBRA

Ch. 2.1 - True or False Label each of the following...Ch. 2.1 - True or False Label each of the following...Ch. 2.1 - True or False Label each of the following...Ch. 2.1 - True or False Label each of the following...Ch. 2.1 - True or False Label each of the following...Ch. 2.1 - Prob. 6TFE Ch. 2.1 - Prob. 7TFE Ch. 2.1 - Prob. 8TFE Ch. 2.1 - Prob. 9TFE Ch. 2.1 - Prob. 10TFE

Knowledge Booster

$Algebra$

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, algebra and related others by exploring similar questions and additional content below.

To prove: If there is an equivalence class [ a ] modulo n , such that x ∈ [ a ] and y ∈ [ a ] , then ( x , n ) = ( y , n ) , where x and y are integers.

Solution Summary: The author explains the equivalence class left[aright] modulo n, where x and y are integers.

Videos

To prove: If there is an equivalence class [a] modulo n, such that x∈[a] and y∈[a], then (x, n)=(y, n), where x and y are integers.

Want to see the full answer?

Chapter 2 Solutions