Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

4 Answers 4

up vote 2 down vote accepted

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

share|improve this answer
    
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

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
"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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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