Mod question

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.

Related Calculus and Beyond Homework Help News on Phys.org

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

Gold Member
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

Homework Helper
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.

Last edited:

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 in to 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

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

Homework Helper
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?

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving