Question

Find all solutions of
\(980x \equiv 1500 (mod 1600)\)
Please , help

Answer 1

When solving Diophantine, I got the final equation is
\(980 (-31) - 1600(-19) =20\)
Multiple both sides by 75, I got
\(980 (-2325) - 1600 (-1425) = 1500\)
But I don' t know how to get the answer from back of the book x = 75 + 80 k

Answer 2

@ganeshie8

Answer 3

You could reduce the amount of work by dividing out any common factors

Answer 4

\(980x \equiv 1500 \pmod {1600}\)

divide 20 through out and get
\(49x \equiv 75 \pmod {80}\)

Answer 5

both congruences are "equivalent"

Answer 6

Can I? I didn't see any theorem or corollary allows me to do that. However, suppose I can, then?

Answer 7

You don't really need a huge theorem to do that, just write out what a congruence means and use divisibility argument

Answer 8

\(980x \equiv 1500 \pmod {1600} \iff 1600 \mid (980x-1500)\)


yes ?

Answer 9

yes

Answer 10

\(980x \equiv 1500 \pmod {1600} \iff 1600 \mid (980x-1500)\)

\(\iff 80*20 \mid 20(49x-75)\)

yes ?

Answer 11

yes

Answer 12

can we say

\(ab \mid ac \iff b \mid c\)

?

Answer 13

yes

Answer 14

\(980x \equiv 1500 \pmod {1600} \iff 1600 \mid (980x-1500)\)

\(\iff 80*20 \mid 20(49x-75)\)

\(\iff 80 \mid (49x-75)\)

yes ?

Answer 15

yes, :)

Answer 16

good :)

Answer 17

Now, I solve this equivalent and the result is the same with original one, right?

Answer 18

Yep.

your original equation is like 2y + 2x = 2

your new equation is like y + x = 1

they have same solutions because they are identical equations

Answer 19

Thank you so much, let me try.

Answer 20

you may double check with wolfram
http://www.wolframalpha.com/input/?i=solve+49x%3D75+mod+80

Answer 21

Question : if we deduce the congruence like above, we miss one solution.
Problem: Solve \(9x\equiv 6~(mod~15)\)
1) Solve as it is: 9x -15y = 6
gcd (9,15) =3
15 = 9 + 6
9 = 6 + 3
6 = (2) 3 + 0
Hence 3 = 9 - 6 = 9 - ( 15 -9) = (2) 9 - 15
Hence 6 = (4) 9 -(2) 15
\(x_0 = 4 \\x = 4 + \dfrac{15}{3}t; t={0,1,2}\)
Hence \(x = \overline 4; x= \overline 9; x =\overline {14}\)
2) deduce \(9x\equiv 6 ~(mod~15)\\3x\equiv 2~(mod~5)\)

That is, we need find 3x -5y = 2
gcd (3,5) =1
5 = 3 + 2 --> 2 = 5 - 3
3 = 2 + 1--> 1 = 3 -2
1 = 3- (5 - 3) = (2) 3 -5
hence 3(4) - 5(2) = 2
\(x_0 = 4: x = 4 +5t: t =\{0,1\}\)
Then \(x = \overline 4 ~~or~~ x=\overline 9\). We miss \(x =\overline {14}\)
@ganeshie8

Answer 22

what makes you think we're missign x=14 ?

Answer 23

@Loser66

Answer 24

if it is mod 5, then x =14 = 4 , but we have to solve for mod 15, hence x = 14 must be one of the solutions. If we make the equivalent congruent as above and solve it, we don't have x =14 as it is in original one.

Answer 25

I see what you're thinking.

For the congruence, \(9x\equiv 6 ~\pmod{15}\), the solution is \(x\equiv 4\pmod{5}\).

How do you express that solution in parameter form ?

Answer 26

@Loser66

Answer 27

@ganeshie8

Answer 28

I don't get your question, x =4 mod 5 , \(x = 4 + 5t\)

Answer 29

Yes, what integers does that solution include ?
Maybe write out first few

Answer 30

1

Answer 31

0

Answer 32

don't wry about the mod,
just write out the integers, x, that satisfy \(9x\equiv 6\pmod{15}\)

Answer 33

x = 4, 9, 14

Answer 34

why only 3 ?
doesn't -1 satisfy the congruence ?

Answer 35

because -1 =4 mod 5

Answer 36

I said, forget about mod

Answer 37

oh, because we have the congruent class, not a concrete number.

Answer 38

and -1 belongs to {14 bar}

Answer 39

write out first few integers, x, that satisfy the given congruence

Answer 40

I'm just asking you to write out first few integer, x, that satisfy the given congruence.

That is a simple question. You don't really need to use mod.

Answer 41

-1,4,6

Answer 42

is it not that when we write out something, we need a mod to calculate ? like if you say 9x = 6 , I have to know on which mod to write out some solutions. If I don't have any mode, how can I know them since 9x =6 mod 2 differ from mod 3, mod 4, mod 5 and so on. ...
I hate to be dummy like this but I do not get even a "simple question" like what you think.

Answer 43

we don't "need" another congruence to write out solutions to a congruence.

Answer 44

Let me write out few solutions to the congruence \(9x\equiv 6\pmod{15}\) :

the integers \(x = 4,9,14,-1,-6\) satisfy above congruence

Answer 45

I think you should teach me all. I can learn quickly. It is better than you ask something you assume that I knew but I didn't. :)

Answer 46

I am pretty sure you knew the theory. It's just that you had never used congruences much, you're finding it difficult to interpret them properly...

Answer 47

As you can see, every element in the set, \(\{4+5t : t\in \mathbb{Z}\}\), is a solution to the congruence \(9x\equiv 6\pmod{15}\)

Answer 48

Sanity is back

Answer 49

But that set form looks ugly when to do arithmetic, so we express the solutions in congruence form instead :
\(x\equiv 4\pmod{5}\)

Answer 50

When we say, \(x\equiv 4\pmod{5}\) is the solution, we're saying that the infinite set \(\{4+5t : t\in \mathbb{Z}\}\) is the solution.

Answer 51

but in class, it is not all t in Z, they are remainder of division by gcd ( a, b) on ax + by = c

Answer 52

I said, forget about mod

Answer 53

ok

Answer 54

the question is about finding the solutions to given congruence

not about how we express them

Answer 55

But if somebody asks you to list out the "incongruent" solutions in mod 15, what would you list ?

Answer 56

then you can say a set of "incongruent" solutions in mod 14 is : \(\{4,9,14\}\)

Answer 57

Somebody else comes up and asks you to list out the "incongruent" solutions in mod 5, then you would give them a set with one element : \(\{4\}\)

Answer 58

Somebody else comes up and asks you to list out the "incongruent" solutions in mod 10, then you would give them a set with one element : \(\{4,9\}\)

Answer 59

As you can see all those answers are same. They all give the set \(\{4+5t : t\in \mathbb{Z}\}\).

Answer 60

\(\{4,9,14\}\) in mod 15

is same as

\(\{4\}\) in mod 5

is same as

\(\{4,9\}\) in mod 10

is same as

\(\{4+5t : t\in \mathbb{Z}\}\)

Answer 61

they all generate the same integers as solutions.
they are just different but equivalent ways to express the solution to congruence \(9x\equiv 6\pmod{15}\)

Answer 62

It doesn't matter how you express the final solution if the textbook doesn't ask you explicitly

Answer 63

Ofcourse simply saying \(x\equiv 4\pmod{5}\) is the solution looks better.

"Congruence" is just a short hand "notation" which makes expressing divisibility statements compact. Nothing more.

Answer 64

It is new to me. I have to digest it completely. Thanks a lot.

Answer 65

np, just ask if something is not clear. i think we are messing with two formats of expressing the solutions :

1) all the solutions of a congruence
2) incongruent solutions under specific mod


you don't "need" to give the solutions in second format. just know that we can simply write out the solution in set form