3
$\begingroup$

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!

$\endgroup$

4 Answers 4

Reset to default
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ 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?! $\endgroup$
    – iCodeLikeImDrunk
    Sep 12, 2012 at 16:04
  • $\begingroup$ @ 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}\}$. $\endgroup$
    – Rod Carvalho
    Sep 12, 2012 at 16:08
  • $\begingroup$ 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? $\endgroup$
    – iCodeLikeImDrunk
    Sep 12, 2012 at 16:16
  • $\begingroup$ @Rob: if x 34, then 6x = 204, how is 204 = 14 % 35? since 14%35 is 14?! sorry, im very confused. $\endgroup$
    – iCodeLikeImDrunk
    Sep 12, 2012 at 16:32
  • $\begingroup$ @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? $\endgroup$
    – iCodeLikeImDrunk
    Sep 12, 2012 at 16:42
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ "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,714,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? $\endgroup$
    – iCodeLikeImDrunk
    Sep 12, 2012 at 16:13
  • $\begingroup$ @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. $\endgroup$
    – Ross Millikan
    Sep 12, 2012 at 16:17
  • $\begingroup$ so then there would 34 solutions to this problem? since all those numbers mod 35 is 14!? $\endgroup$
    – iCodeLikeImDrunk
    Sep 12, 2012 at 16:33
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .