Mod Question: Solving 128x ≡ 833 (mod 1001) and Finding GCD = 1

[Isaak DeMaio]

1. 128x ≡ 833 (mod 1001)


3. GCD = 1. I don't really understand how to find this one. I find it just by guessing numbers, but this is just getting on my nerves.
I think a 7U-V has to do with it, but I'm not sure.

 

[Robert1986]

1. 128x ≡ 833 (mod 1001)


3. GCD = 1. I don't really understand how to find this one. I find it just by guessing numbers, but this is just getting on my nerves.
I think a 7U-V has to do with it, but I'm not sure.

I'm inferring that your task is to determine x; is this accurate? I will write this post as if that is your task.


First, what do you think it means for two integers to be congruent mod n? If you don't know this, look it up and come back. It seems you know what it is (since you have been guessing numbers) so you can probably go to the next step.


Second, you say that GCD=1. This is meaningless. This is like saying the quotient is 1, or the product is 1. I assume that what you mean is GCD(128,1001)=1; is this accurate? (Well, I know it is true, but is that what you meant to say?)


Third, the congruence modulo n relation is an equivalence relation which means that it behaves in a very nice, expectable manner. In particular, it is symmetric, transitive and reflexive. So, how would you go about solving this equation:
$$128x = 833$$

You would divide both sides by 128, right? Well, another way of saying "divide by 128" is saying "multiply by the multiplicative inverse of 128". To solve your stated congruence, you are going to do something similar: you are going to multiply both sides of the congruence by the multiplicative inverse of 128 (mod 1001). In other words, let z be the multiplicative inverse of 128 mod 1001. This means that 128z=1(mod1001).

So, once you have found z, multiply both sides of your congruence by z. Now, all you have to do is find z. YOu know that it exists because gcd(128,1001)=1.

 

[Isaak DeMaio]

That had nothing to do with finding x at all...

 

[Robert1986]

That had nothing to do with finding x at all...

Your post or mine? I have no idea what you were trying to do in your post. My post most certainly has to do with finding x. Did you read it?


Let me see if I can spell it out for you even more. Let z be the inverse of 128 modulo 1001

Take this congruence:
$$128x \equiv 883 mod 1001$$

Now multiply both sides by z:
$$128xz \equiv 883z mod 1001$$
which reduces to:
$$x \equiv 883x mod 1001$$

Viola! So, as you can see, my post most certainly has to do with finding x.

And here's a hint: Actually ask a question in your OP.

 

[Robert1986]

That had nothing to do with finding x at all...

One more thing, what is "a 7U-V"?

 

[Isaak DeMaio]

And here's a hint: Actually ask a question in your OP.

The question is what is X.
128x congruent 833 (mod 1001)

Adding a Z has nothing to do with finding X.

(128 * X) - 833 can be divided by 1001 evenly. But what is X is my question. I can't figure it out.

 

[Robert1986]

The question is what is X.
128x congruent 833 (mod 1001)

Adding a Z has nothing to do with finding X.

(128 * X) - 833 can be divided by 1001 evenly. But what is X is my question. I can't figure it out.

...which is why I explained how to do math modulo some integer.


When did I ever add a Z? I explained that when you multiply 128 by z, the product is 1 mod 1001. I then explained that you could multiply both sides of the congruency by z to obtain x = 883z (mod 1001).


Let me see if I can work out an example.

Let's say you have the congruence 3x = 4 (mod 5).

First, we see that gcd(3,5)=1 so we know that 3 has a multiplicative inverse modulo 5. In this case, the inverse of 3 modulo 5 is 2 (this is the "z" i am talking about.) So, now I am going to multiply both sides of my congruence by 2:
3*2*x = 4 *2 (mod 5)

Since 3*2 = 1 (mod 5) this reduces to:
3*2*x = x = 8 = 3 (mod 5)

so, x is congruent to 3 mod 5. To check, we see that:

3x = 3*3 = 9 = 4(mod 5)

Do you understand, now?

 

[Isaak DeMaio]

Do you understand, now?

No because that problem is too easy and you did so much unnecessary work. Why not just do it the way I am suppose to do it which I don't understand, which I'll actually understand if you actually show it that way.

 

[Robert1986]

No because that problem is too easy and you did so much unnecessary work.

As opposed to your guess work? I know my example was easy. That wasn't my question.

Why not just do it the way I am suppose to do it which I don't understand, which I'll actually understand if you actually show it that way.

Because up to this point the content of your posts has been sparse and arrogant. You haven't actually told me what it is you don't understand. You have only told me that I am wrong. I am trying to show you how to solve congruences like this, but you don't seem to care. You want me to show it a the way that you are supposed to do it, but I have no idea what that way is. Now, please read my first response. All I am saying is that to find x here, you can do very similar things that you did to find x in the equation 128x=883. Instead of dividing both sides by 128, you need to multiply both sides by the inverse of 128 modulo 1001.

BTW, I solved your problem, using my method in about 5 minutes. How long have you been working on it?

 

[Isaak DeMaio]

No because that problem is too easy and you did so much unnecessary work.

As opposed to your guess work? I know my example was easy. That wasn't my question.


Because up to this point to content of your posts has been sparse and arrogant. You haven't actually told me what it is you don't understand. You have only told me that I am wrong. I am trying to show you how to solve congruences like this, but you don't seem to care. You want me to show it a the way that you are supposed to do it, but I have no idea what that way is.

BTW, I solved your problem, using my method in about 5 minutes. How long have you been working on it?

Then why are you still replying?

And you most likely didn't haha

 

[Char. Limit]

Tch, if you're going to ask a question listen to the answer instead of telling him he's wrong. If you know he's wrong, why do you even have a question, since you obviously know the answer? After all, you must be right in order to know that he is wrong. So what's the answer, huh?

His method worked fine when I tried it too. I think if you tried it instead of just saying "you're wrong", it would work for you too.

Oh, and you still haven't told us how you are "supposed to do it".

 

[Robert1986]

No because that problem is too easy and you did so much unnecessary work.

Then why are you still replying?

And you most likely didn't haha

Because your arrogance and unwillingness to learn anything interests me.
$$x \equiv 46 (mod 1001)$$

I found it my method, you know, the one you refuse to learn.

 

[Isaak DeMaio]

The check doesn't even work for 46

 

[Robert1986]

The check doesn't even work for 46

Indeed, you are correct. I was solving this cogruence:
128*x=883 (mod 1001)

For your congruence it is:
x=812

Since 128*812=103936 and 103936-833=103103=103*1001

Now, are you having fun punching in numbers in your calculator? Are you ready to learn something? Would you actually like to learn how to calculate inverses modulo n? Or, would you care to explain how you are "supposed" to do it so that I can explain that?

 

[HallsofIvy]

Your original problem was 128x ≡ 833 (mod 1001).

That is the same as saying that 128x= 833+ 1001y or 128x- 1001y= 833 for some integer y.

1) 128 divides into 1001 7 times with remainder 105: 1001- 7(128)= 105
2) 105 divides into 128 once with remainder 23: 128- 105= 23.
3) 23 divides into 105 4 times with remainder 13: 105- 4(23)= 13.
4) 13 divides into 23 once with remainder 10: 23- 13= 10.
5) 10 divides into 13 once with remainder 3: 13- 10= 3.
6) 3 divides into 10 3 times with remainder 1: 10 -3(3)= 1.

Replace the "3" in 10- 3(3) = 1 with 13- 10 from (5):
10- 3(13- 10)= 4(10)- 3(13)= 1.

Replace the "10" in that with 23- 13:
4(23- 13)- 3(13)= 4(23)- 7(13)= 1.

Replace the "13" in that with 105- 4(23):
4(23)- 7(105- 4(23)= 32(23)- 7(105)= 1.

Keep working back that way until you get to "p(128)- q(1001)= 1" for integers p and q. The multiply the entire equation by 833 to get (833p)(128)- (833q)(1001)= 833.

Your x will be 833p (or equivalent to it mod 1001).

 

[Robert1986]

Your original problem was 128x ≡ 833 (mod 1001).

That is the same as saying that 128x= 833+ 1001y or 128x- 1001y= 833 for some integer y.

1) 128 divides into 1001 7 times with remainder 105: 1001- 7(128)= 105
2) 105 divides into 128 once with remainder 23: 128- 105= 23.
3) 23 divides into 105 4 times with remainder 13: 105- 4(23)= 13.
4) 13 divides into 23 once with remainder 10: 23- 13= 10.
5) 10 divides into 13 once with remainder 3: 13- 10= 3.
6) 3 divides into 10 3 times with remainder 1: 10 -3(3)= 1.

Replace the "3" in 10- 3(3) = 1 with 13- 10 from (5):
10- 3(13- 10)= 4(10)- 3(13)= 1.

Replace the "10" in that with 23- 13:
4(23- 13)- 3(13)= 4(23)- 7(13)= 1.

Replace the "13" in that with 105- 4(23):
4(23)- 7(105- 4(23)= 32(23)- 7(105)= 1.

Keep working back that way until you get to "p(128)- q(1001)= 1" for integers p and q. The multiply the entire equation by 833 to get (833p)(128)- (833q)(1001)= 833.

Your x will be 833p (or equivalent to it mod 1001).

Was this in response to me or the OP? If it is in response to me, this is how I found the inverse of 128 mod(1001). If it is in response to the OP, you are probably wasting your breath.


I had orginally solved the problem for 128*x = 883 mod(1001) (using the extended eucilidean algorithm to find the iverse 128 mod (1001)), then Isaak informed me that my solution was worng. It was then that I realized I had solved the wrong congruence. But, as I said, x=812 (or whaterver it was) is the solution to 128x=833 (mod 1001)

 

[Isaak DeMaio]

He knows how to do it the way I'm suppose too. Thanks for the help Broham.

 

[Isaak DeMaio]

And you spelled "wrong" wrong. The R is suppose to come before the O.

 

[yeongil]

And you spelled "wrong" wrong. The R is suppose to come before the O.

You shouldn't post things like this, especially since you made mistakes yourself in your previous post:

He knows how to do it the at I'm suppose too.

Huh? What are you saying?

 

[Isaak DeMaio]

You shouldn't post things like this, especially since you made mistakes yourself in your previous post:



Huh? What are you saying?

Erroneous.

 

[Robert1986]

He knows how to do it the way I'm suppose too. Thanks for the help Broham.

You never told me how you were supposed to do it; how I was I supposed to know.


BTW, the way Bohram did it was the EXACT WAY that I was doing it, only I gave some more theory so that PERHAPS you could have solved more problems.


Just one question: Why were you so opposed to learning it my way? Why can't you open your mind a tad?


Like I said, I solved your problem in about 5 minutes (using the method Bohram explained). If you had just looked into what I was saying, you wouldn't have wasted so much time.

Here is a hint: If you want people to tell you how to do something in a certain way, you have to EXPLAIN what method you want to use.

 

[Robert1986]

Erroneous.

Did the forum just become a Wedding Crashers scence?

 

[Robert1986]

And you spelled "wrong" wrong. The R is suppose to come before the O.

Oh yes, please correct someone's typo, you are certainly in a position to do so. You do realize that your OP makes almost no sense, mathematical or otherwise. What the heck does GCD=1 mean? What is "a 7U-V"?

I'll bet you still don't even understand why the fact that gcd(128,1001)=1 is relevant. Do you? I would be more than happy to exlpain.

 

[HallsofIvy]

He knows how to do it the way I'm suppose too. Thanks for the help Broham.

Who's Broham?

 

[Isaak DeMaio]

Did the forum just become a Wedding Crashers scence?

You mean scene?

 

[Robert1986]

You mean scene?

Haha, once again, you find a typo and go after it. Nevermind the fact that you have shown nothing but a brutal combination of ignorance and arrogance throughout this entire thread, the important thing is that the people who are trying to help you made some typos.


BTW, you have made several typos, yourself, so you are certainly in no position to critique my grammar. Furthermore, you have routinely committed the far more serious error of being willfully ignorant and unwilling to learn and making no mathematical sense.


I'd still like to know what you think GCD=1 means. Oh yeah, I still haven't figured out what the heck "7U-V" is supposed to be.

 

[Isaak DeMaio]

GCD means amount of solutions.

2nd the U,V can be A,B
1001=A 128=B
1001/128=7 R105. 105=1001 - 7(128) A-7B
128/105=1 R23. 23=128-105. B - (A-7B)= -A+8B
105/23=4 R13. 13=105- 4(23). A-7B - 4(-A+8B)[4A-32B] = 5A-39B
23/13=1 R10. 10=23-13. -A+8B - 5A-39B = -6A+47B
13/10=1 R3. 3=13-10. 5A-39B+6A-47B = 11A-86B
10/3=3 R1. 1=10- (3)3. -6A+47B - (3) 11A-86B [-33A+258B] = -39A+305B
3/1= 3 R0.

I have no idea what to do with those though. HallsofIvy is probably the only person to understand this way, since he basically did it that way.

 

[Isaak DeMaio]

GCD = 1 which means there is one solution

 

[Robert1986]

GCD means amount of solutions.

2nd the U,V can be A,B
1001=A 128=B
1001/128=7 R105. 105=1001 - 7(128) A-7B
128/105=1 R23. 23=128-105. B - (A-7B)= -A+8B
105/23=4 R13. 13=105- 4(23). A-7B - 4(-A+8B)[4A-32B] = 5A-39B
23/13=1 R10. 10=23-13. -A+8B - 5A-39B = -6A+47B
13/10=1 R3. 3=13-10. 5A-39B+6A-47B = 11A-86B
10/3=3 R1. 1=10- (3)3. -6A+47B - (3) 11A-86B [-33A+258B] = -39A+305B
3/1= 3 R0.

I have no idea what to do with those though. HallsofIvy is probably the only person to understand this way, since he basically did it that way.

Nope. The GCD is the greates common divisor of two numbers. In the case of the congurence in x:

ax = b (mod n)

there are solutions for ix if and only if gcd(a,n) divides b, in which case there are exactly gcd(a,n) incongruent solutions.

I have never heard the method you used called hte "7U-V" method. This is just the extended eucildiean algorithm. This is how you calculate inverses modulo n. If you had asked me how to do that, I could have explained. Instead, you just told me my method was wrong.

 

[Isaak DeMaio]

Nope. The GCD is the greates common divisor of two numbers. In the case of the congurence in x:

ax = b (mod n)

there are solutions for ix if and only if gcd(a,n) divides b, in which case there are exactly gcd(a,n) incongruent solutions.

I have never heard the method you used called hte "7U-V" method. This is just the extended eucildiean algorithm. This is how you calculate inverses modulo n. If you had asked me how to do that, I could have explained. Instead, you just told me my method was wrong.

Uhh... The GCD(128,1001) Does in fact mean there is only one solution to 128x=833(mod 1001).

Example in proving GCD shows how many solutions...
66x=100(mod 11). GCD(66,11) = 11. 100/11 = 9.0909090909... Since C/GCD is a decimal, there are no solutions for X.

 

[Isaak DeMaio]

Uhh... The GCD(128,1001) Does in fact mean there is only one solution to 128x=833(mod 1001).

Example in proving GCD shows how many solutions...
66x=100(mod 11). GCD(66,11) = 11. 100/11 = 9.0909090909... Since C/GCD is a decimal, there are no solutions for X.

And since 833/1, in the original problem, turns out to be 833, a whole number, it proves there IS a solution, and only one solution, which you figured out to be 812.

 

[Robert1986]

Uhh... The GCD(128,1001) Does in fact mean there is only one solution to 128x=833(mod 1001).

Example in proving GCD shows how many solutions...
66x=100(mod 11). GCD(66,11) = 11. 100/11 = 9.0909090909... Since C/GCD is a decimal, there are no solutions for X.

Yes, that is correct, but that is not the definition of gcd.

 

[Isaak DeMaio]

Yes, that is correct, but that is not the definition of gcd.

Your question was not "Define GCD." Your question was "do you even know what GCD=1 means"
And I told you what it meant. So what are you arguing there?

How do I find the complete system of residues modulo 5?
I don't really understand how to find them.

 

[Mark44]

Your question was not "Define GCD." Your question was "do you even know what GCD=1 means"
And I told you what it meant. So what are you arguing there?

Without context, GCD = 1 is meaningless. It's something like writing + = 3.

 

[Robert1986]

Your question was not "Define GCD." Your question was "do you even know what GCD=1 means"
And I told you what it meant. So what are you arguing there?

How do I find the complete system of residues modulo 5?
I don't really understand how to find them.

Usually, a system of residues modulo n (n an integer) is defined this way:
A complete system of residues modulo m is a set of integers such that every integer is congruent modulo m to exactly one integer of the set.

OK, so cutting through the rather convoluted English, what does this mean? Let's look at your example of a system of residues modulo 5.

Now, first we note that two integers m and n are congruent modulo 5 if and only if the remainder of m after dividing m by 5 is equal to the remainder of n after dividing n by 5. So 1/5 = 0 plus a remainder of 1 and 6/5 = 1 plus a remainder of 1. So we say that 1 is congruent to 6 modulo 5 and write it this way: 1 = 6 (mod 5). Also, we see that 16=11=6=1 (mod 5).


Now, for any integer n, how many different congruences mod n are there? It is easy to see that there are n different ones: {0,1,...,n-1}. In fact, {0,1,...,n-1} is a complete system of residues mod n; it even has a special name: least nonnegative residues mod n.


So, to find a complete system of residues mod n, all you need to do is find a set of n integers such that each integer is congruent to a unique number mod n. For 5, the set {0,1,2,3,4} is a system of residues mod 5 as is {0,11,22,103,99} but {10,11,12,27,39} are not since 12=27(mod 5).


So, to put it another way, a complete system of residues mod 5 is a set of integers such that each integer in the set has a different remainder upon division by 5.