# How many solutions does equation $6x=14 \bmod 35$ in $\mathbb{Z}/35\mathbb{Z}$ have?

Yes, this is a homework problem. And no, I'm not asking for the answer to this.

I just want to understand how to tackle this type of problem. What are the steps towards finding the solutions? My class is not much help and I am lost!

Any help is appreciated!

-
add comment

## 4 Answers

Here's an extremely short Haskell GHCi session:

Prelude> [ x  | x <- [0..34], (6 * x) mod 35 == 14 ]
[14]


Therefore, $x = 14$. Why? Note that $6 \times 14 = 84 = (2 \times 35) + 14$.

-
correct me if im wrong, so we have that 14mod35 = 14, and 84 is a solution because 84%35 = 14? how do i find other solutions to this problem? i edited the question. please take a look. thank you! <br/><br/> since 14%35 = 14 in Z35, then wouldnt there be an infinite number of solutions? since there tons of numbers that mod 35 is 14?! –  yao jiang Sep 12 '12 at 16:04
@ Yao: Isn't $\mathbb{Z} / 35 \mathbb{Z}$ a finite ring? How can there be an infinite number of solutions? If you want to find all integers that satisfy the equation, then the solution set is $\{ 14 + 35 n \mid n \in \mathbb{Z}\}$. –  Rod Carvalho Sep 12 '12 at 16:08
so the solution to Z/35Z should be {14+35n | n ∈ Z35}? from what i remember from class, Z/35Z = {0..34}, so i should only compute this up to n = 34? –  yao jiang Sep 12 '12 at 16:16
@Rob: if x 34, then 6x = 204, how is 204 = 14 % 35? since 14%35 is 14?! sorry, im very confused. –  yao jiang Sep 12 '12 at 16:32
@Rob, last question, is x=14 the ONLY solution, or is 14 the total number of solutions to 6x = 14 mod 35 in Z/35Z? –  yao jiang Sep 12 '12 at 16:42
show 1 more comment

In this case, we note that $6$ is a unit in $\textbf{Z}/35 \textbf{Z}$ since $\gcd(6,35)=1$. So multiplying both sides of your equation by the inverse of $6$ mod $35$ (which happens to be $6$, we see that we obtain a unique solution, $x = 14*6 = 14 \mod 35$.

In general, if you look at an equation of the form $ax = b \mod M$, the number of solutions is governed by gcd(a,M). Play around with a few small (calculable by hand) examples to see if you can figure out what's going on.

-
add comment

For small values, you can just look. A spreadsheet will make it easy. If you are looking by hand, note that if you find a $y$ such that $6y$ is a factor of $14 \pmod {35}$, you can just multiply. In this case, when you try $y=6$ and discover $6\cdot 6 \equiv 1 \pmod {35}$, you can multiply both sides by $14$ and find $14$. Alternately, you can just try $14, 14+35, 14+2\cdot 35 \ldots$ looking for a multiple of $6$.

For larger values, the Extended Euclidean algorithm is your friend.

-
"14,14+35,14+2⋅35…" how high does this go? up to 14+35*35?<br/><br/> so 14 is a possible answer, since 14*6=84, 84%35 = 14 = 14%35!? <br>14+35= 49, 49%35 = 14 also... so from this, the possible solutions are (14,49,84,119,154,189,224,259,294,329,364,399,434,469,504,539,574,609,644,679,71‌​4,749,784,819,854,889,924,959,994,1029,1064,1099,1134,1169) i wrote a python code to run up to 35.. do i go over 35 or it should be {0..34} since it is Z/35Z? –  yao jiang Sep 12 '12 at 16:13
@yaojiang: As you are looking for multiples of $6$ you only need try $6$ of them before you find one or know there isn't one. Since $35=0 \pmod {35}$ any value $14+35k$ will work fine. –  Ross Millikan Sep 12 '12 at 16:17
so then there would 34 solutions to this problem? since all those numbers mod 35 is 14!? –  yao jiang Sep 12 '12 at 16:33
add comment

I would solve the problem using Euclid's Algorithm.

6x = 14 (mod 35)

-> 6x - 14 = 35k -> 6x + 35y = 14 (I just changed variables from k to y).

Using the equations derived through finding the gcd of 6 and 35, you find that one solution is x = 14 and y = -2, so one solution is x = 14. Of course, you can get other solutions but you will be working mod 35 so these will be the same.

-
add comment