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

 Number Theory Number Theory Math Forum

 January 29th, 2017, 11:49 AM #1 Senior Member   Joined: Jan 2013 From: Italy Posts: 152 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!
January 29th, 2017, 01:35 PM   #2
Senior Member

Joined: Aug 2012

Posts: 891
Thanks: 166

Quote:
 Originally Posted by beesee 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.

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,254 Thanks: 561 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{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}$
 February 17th, 2017, 09:32 AM #5 Math Team   Joined: Dec 2013 From: Colombia Posts: 6,399 Thanks: 2105 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

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Top