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

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

 

[Isaak DeMaio]

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.

So would it be like 5=0(mod5), 1=1(mod5), 12=2(mod5), 28=3 (mod5)

How exactly do you show the complete system?

 

[Robert1986]

So would it be like 5=0(mod5), 1=1(mod5), 12=2(mod5), 28=3 (mod5)

How exactly do you show the complete system?

Well, any complete system of residues mod n has n elements. So, if you add 19 = 4(mod 5) you would have a complete system. As far as showing that it is complete, if you are making up some set, yourself all you need to do is say "Hey, I've got this set of n elements and no two are congruent modulo n, so it is a complete system of residues." However, let's assume that you were asked the following:

Let p be a prime number and let a be less than p. Does the following set form a complete system of residues mod p:
1a,2a,3a,...,(p-1)a

To show this you need to demonstrate that there are p elements in the set and that no two elements are congruent mod p. Clearly there are p elements. If there are two congruent mod p, then we have an r and an s such that ra=sa (mod p). However, since gcd(a,p)=1, a has an inverse so this implies that r = s (mod p), which is a contradiction (why?).


So, the method used to prove that a set is a complete system of residues mod n depends heavily on the set you are trying to prove.

 

[Isaak DeMaio]

Well, any complete system of residues mod n has n elements. So, if you add 19 = 4(mod 5) you would have a complete system. As far as showing that it is complete, if you are making up some set, yourself all you need to do is say "Hey, I've got this set of n elements and no two are congruent modulo n, so it is a complete system of residues."

So the question "find the complete system of residues modulo 5." Would just be a statement?

 

[Robert1986]

Yes. The solution to your question is: {0,1,2,3,4}. Is this a homework question? If so, could you give the definition that your book gives for "complete system of residues". The reason that I ask is because I want to make sure that your definition is exactly what my definition is.

 

[Isaak DeMaio]

Yes. The solution to your question is: {0,1,2,3,4}. Is this a homework question? If so, could you give the definition that your book gives for "complete system of residues". The reason that I ask is because I want to make sure that your definition is exactly what my definition is.

It's not a book question. It's a written out question, like a take home review/prep thing. :(

 

[Robert1986]

It's not a book question. It's a written out question, like a take home review/prep thing. :(

Then I guess your instructor just wants something like this: {0,1,2,3,4} which is a complete system of residues mod 5.

 

[Isaak DeMaio]

Then I guess your instructor just wants something like this: {0,1,2,3,4} which is a complete system of residues mod 5.

could it also be: 0=mod5, 1=mod5 etc...

 

[Mark44]

could it also be: 0=mod5, 1=mod5 etc...

mod5 by itself doesn't mean anything.
The numbers 0, 5, 10, 15, 20, ..., 5n, ... are all in the congruence class 0 modulo 5.
The numbers 1, 6, 11, 16, 21, ..., 5n + 1, ... are all in the congruence class 1 modulo 5.
The numbers 2, 7, 12, 17, 22, ..., 5n + 2, ... are all in the congruence class 2 modulo 5.
The numbers 3, 8, 13, 18, 23, ..., 5n + 3, ... are all in the congruence class 3 modulo 5.
The numbers 4, 9, 14, 19, 24, ..., 5n + 4, ... are all in the congruence class 4 modulo 5.
I haven't included the negative integers, but each of them is in one of the congruence classes.

 

[Isaak DeMaio]

I"m lost on how to write the answer.

 

[Mark44]

Just like Robert1986 did in post #41.

 

[Isaak DeMaio]

It seems a bit bland though.

 

[Mark44]

Bland is better than wrong...

 

[Robert1986]

It seems a bit bland though.

It is, but the question, itself, is a bit bland. This is why I was wondering if perhaps your instructor (or whoever wrote the question) meant something different. Just out of curiosity, what class is this for?

 

[Isaak DeMaio]

It is, but the question, itself, is a bit bland. This is why I was wondering if perhaps your instructor (or whoever wrote the question) meant something different. Just out of curiosity, what class is this for?

Theory of Numbers. lawlz