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!

4 Answers 4

1

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.

4

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.

2

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

  • 0
    @Rob: so 14 it is! thanks!2012-09-12
1

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.

  • 0
    so then there would 34 solutions to this problem? since all those numbers mod 35 is 14!?2012-09-12