Question

3. (Linear Congruence). An equation in integers of the form ax=b (mod m) is called a linear congruence. We want to find an integer x that will satisfy it. (Note that ax=b (mod m) is equivalent to saying ax-b=nm for some integer n.
a) Prove that if (a, m) = 1 then there is always a solution. (Hint: express the gcd as a linear combination and multiply by b.).
b) For 56 and 15 use the Euclidean algorithm to express the gcd 1= (56, 15) as a linear combination 56s+15t=1.
c) Use part b to find a value of x so that 15x=7 (mod 56).

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

The proof has two parts: 1) existence of a solution and 2) uniqueness of the solution.
For the existence part, we must effectively build the solution.
Since (a,m)=1 => exists integers p and q such that a*p+m*q=1
We multiply the previous relation with b in both sides => b*a*p +b*m*q= b
Reducing the last equation modulo m => b*a*p = b (mod m) which is equivalent with a(bp)= b (mod m)
...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

Abstract Algebra Essay
Homework Solution
$75.00
Abstract Algebra
Galois Theory
Field Extensions
Algebraic Number
Splitting Fields
Field Automorphisms
Factorization Questions
Homework Solution
$40.00
Factorization
Polynomial
Mathematics
Abstract Algebra
Irreducibility
PID
UFD
Tensor Products of Modules
Homework Solution
$60.00
Mathematics
Algebra
Tensor Product
Modules
Functions
Multiplication
Constants
Formal Sums
Space of Rings
Relations
Vector Spaces
Linear Compositions
Simplification Rules
Cyclic Group Questions
Homework Solution
$10.00
Generator
Cyclic Group
Isomorphism
Identity Element
Inverse
Modulo
Homomorphism
Property
Three Sylow Theorems
Homework Solution
$25.00
Mathematics
Sylow Theorems
Proofs
Subsets
Partitions
Subgroups
Maxima
Minima
Functions
Automorphism
Operations
Functions
Get help from a qualified tutor
Live Chats