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
$\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 '12 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 '12 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 '12 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 '12 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 '12 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 '12 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 '12 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 '12 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.