
Number Theory Number Theory Math Forum 
 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  3x2 \Rightarrow \\ 3x2 = 7q \Rightarrow \\ 3x = 7q+2$ $x=1) \quad 3(1)= 7q+2 \Rightarrow 7q = 32 \Rightarrow 7q = 1 \Rightarrow q = \frac{1}{7} \notin \mathbb{Z} \\ x=2) \quad 3(2)=7q+2 \Rightarrow 7q = 62 \Rightarrow 7q = 4 \Rightarrow q = \frac{4}{7} \notin \mathbb{Z} \\ x=3) \quad 3(3) = 7q+2 \Rightarrow 7q = 92 \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! 
January 29th, 2017, 01:35 PM  #2  
Senior Member Joined: Aug 2012 Posts: 1,620 Thanks: 411  Quote:
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...rcongruences/ You did get the correct answer with your method. $4 + 7 = 3$ so that should be in your list. Last edited by Maschke; January 29th, 2017 at 01:56 PM.  
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. 
February 17th, 2017, 05:18 AM  #4 
Newbie Joined: Aug 2015 From: china Posts: 6 Thanks: 4 
$\displaystyle y=\frac{3x2}{7}=\frac{3(x3)+7}{7}=\frac{3(x3)}{7}+1$ namely $\displaystyle 7x3$ $\displaystyle x3=7k,x=7k+3,k\in{Z}$ 
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*} 

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 