My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree3Thanks
  • 3 Post By Maschke
Reply
 
LinkBack Thread Tools Display Modes
January 29th, 2017, 11:49 AM   #1
Senior Member
 
Joined: Jan 2013
From: Italy

Posts: 154
Thanks: 7

Congruence 3x ≡ 2 (mod 7). Find all $x \in Z$

Hi,

I have to find all $x \in \mathbb{Z}$ that satisfy the following congruence:
$3x \equiv 2 \mbox{ (mod 7) }$

I think that for search every x I have to go by attempts, and I think that there isn't any "automatic" procedure to find all of them. What do you think?

However, I have tried this, considering the definition of congruence:
$7 | 3x-2 \Rightarrow \\ 3x-2 = 7q \Rightarrow \\ 3x = 7q+2$

$x=1) \quad 3(1)= 7q+2 \Rightarrow 7q = 3-2 \Rightarrow 7q = 1 \Rightarrow q = \frac{1}{7} \notin \mathbb{Z} \\
x=2) \quad 3(2)=7q+2 \Rightarrow 7q = 6-2 \Rightarrow 7q = 4 \Rightarrow q = \frac{4}{7} \notin \mathbb{Z} \\
x=3) \quad 3(3) = 7q+2 \Rightarrow 7q = 9-2 \Rightarrow 7q=7 \Rightarrow q = \frac{7}{7} = 1 \in \mathbb{Z}$
etc...

So $x=3$ a element in Z we want, and in an analog way we can find -4, 10 etc....

In my book the given answer is:
$3 + 7 \mathbb{Z} = \left \{..., -4,3,10,... \right \}$
From what springs that writing? Is it a misprint? Please, can you explain me better? Thanks!
beesee is offline  
 
January 29th, 2017, 01:35 PM   #2
Senior Member
 
Joined: Aug 2012

Posts: 1,620
Thanks: 411

Quote:
Originally Posted by beesee View Post
Hi,

I have to find all $x \in \mathbb{Z}$ that satisfy the following congruence:
$3x \equiv 2 \mbox{ (mod 7) }$
By inspection $3$ is a solution, since $3 \times 3 - 2 = 7$.

Then all solutions are $3 + 7 \mathbb Z$. That's ad hoc but in this case it's the best way.

This page describes the general method, which is overkill when you can see the solution by looking at it.

https://exploringnumbertheory.wordpr...r-congruences/

You did get the correct answer with your method. $-4 + 7 = 3$ so that should be in your list.
Thanks from greg1313, beesee and topsquark

Last edited by Maschke; January 29th, 2017 at 01:56 PM.
Maschke is online now  
February 17th, 2017, 04:45 AM   #3
Math Team
 
Joined: Jan 2015
From: Alabama

Posts: 2,820
Thanks: 750

3x ≡ 2*(mod 7)* means that 3x = 7n + 2 for some n. That is the same as the "Diophantine equation" 3x - 7n = 2 for x and n integers. There is a standard way or solving such equations: Observe that 3 divides into 7 twice with remainder 1: 7 - 2(3) = 1. Multiplying both sides by 2, 7(2) - 3(4) = 3(-4) - 7(-2) = 2. So one solution is x = -4, n = -2. But it is easy to see that x = -4 + 7k, n = -2 + 3k is also a solution for every integer k: 3(-4 + 7k) = -12 + 21k while -7(-2 + 3k) = 14 - 21k. Adding those gives 2 for all k.

In particular, taking k = 1 gives x = 3, between 0 and 7. 3x ≡ 2*(mod 7)* for x = 3 (mod 7)

Last edited by skipjack; February 17th, 2017 at 11:32 AM.
Country Boy is offline  
February 17th, 2017, 05:18 AM   #4
Newbie
 
Joined: Aug 2015
From: china

Posts: 6
Thanks: 4

$\displaystyle y=\frac{3x-2}{7}=\frac{3(x-3)+7}{7}=\frac{3(x-3)}{7}+1$
namely
$\displaystyle 7|x-3$
$\displaystyle x-3=7k,x=7k+3,k\in{Z}$
fengnr is offline  
February 17th, 2017, 09:32 AM   #5
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,031
Thanks: 2342

Math Focus: Mainly analysis and algebra
An analytic solution goes as follows:
$5 \times 3 = 15 \equiv 1 \pmod 7$ (this result can be found by exhaustive search for the multiplicative inverse of 3).

Therefore
\begin{align*}
5 \times 3x & \equiv 5 \times 2 \pmod 7 \\
15x &\equiv 10 \pmod 7 \\
x &\equiv 3 \pmod 7
\end{align*}
v8archie is online now  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
, congruence, find, mod



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
congruence gerva Number Theory 6 August 12th, 2016 12:26 AM
Congruence Sara Algebra 1 November 16th, 2014 10:20 AM
Congruence s.a.sajib Number Theory 9 April 8th, 2013 07:28 AM
congruence justjones Algebra 2 March 13th, 2013 03:38 PM
Congruence Fernando Number Theory 3 May 15th, 2012 09:20 AM





Copyright © 2017 My Math Forum. All rights reserved.