Question regarding modular arithmetic from discrete math

[f24u7]

Homework Statement

Homework Equations

a. I know that x*a mod y should be the same as y*b mod x but I don't understand why
b. I know that an inverse can be constructed because x and y are mutually prime and gcd(x,y) = 1 , but I have no clue at what pair x and m is possible
c. I have no idea how to do c.)

The Attempt at a Solution

I look at the notes from lecture, and I look at some discrete math textbook (we don't have a textbook) but still have no clue,
I also search the web regarding modular arithmitic.

Any hint regarding this subject would be really appreciated.

 

[rcgldr]

You can use attachments for images here at physics forums rather than using a photo website with ads.

a. I know that x*a mod y should be the same as y*b mod x but I don't understand why

part a) is asking about x*a mod y and the inverse of y*b mod x.

I'm not sure about the syntax being used, what does Z.a,b mean? Usually Z_p refers to a set of integers modulo p.

 

[f24u7]

You can use attachments for images here at physics forums rather than using a photo website with ads.

part a) is asking about x*a mod y and the inverse of y*b mod x.

I'm not sure about the syntax being used, what does Z.a,b mean? Usually Z_p refers to a set of integers modulo p.

I think you miss the order, the original statement just says that there exist a, b that exist in the set of integers in which a and b is not equal to zero

 

[rcgldr]

I think you miss the order, the original statement just says that there exist a, b that exist in the set of integers in which a and b is not equal to zero

That's what I thought the Z meant, but it shows as Z.a,b, so I wasn't sure. Again part a) is asking about the inverse for the y·b mod x. It's been a long time since I worked with finite field math and that was for work with error correction codes.

 

[f24u7]

Sorry, I still don't quite understand how to solve the question, can you give me more hint?

 

[rcgldr]

It appears there are some mistakes in the way the problem is worded. My guess is that what is meant is that x and y are mutually prime, and that there exists a pair of integers a and b (neither = 0) so that 1 = a·x + b·y .

so for part a):

x·a = 1 - b·y
x·a mod y = (1 - b·y) mod y = 1

y·b = 1 - a·x
y·b mod x = (1 - a·x) mod x = 1

Then part a) asks for the inverse of y·b mod x, and the inverse of 1 is 1.

part b) gets confusing because it then switches to using x and m in the same manner that it previously used a and x, substituting x for a, and m for x and apparently incorrectly defines an inverse function. I think it should be asking if part a) can be used to construct a function Inv(x,m) so that (x·Inv(x,m)) mod m = 1 (as opposed to x·Inv(x,m) = 1 mod m). Using the previous symbol names, this would be the equivalent of constructing a function Inv(a,x) so that (a·Inv(a,x)) mod x = 1.

The only method I know of to find Inv(a,x) is an iterative process similar to the Euclid algorithm for finding the greatest common divisor.

Does this help?

 

[rcgldr]

A follow up, not sure if you're still working on this problem. I think the wording of part a) was messed up a bit and should left out the word "inverse". Would have been nice if there was a class handout since there is no textbook.

So what I think the reworded questions should be:

part a) ... so what does this tell us about x·a mod y and y·b mod x ? What is the relationship between x and a? What is the relationship between y and b?

part b) What relationship between x and m is required in order to define a working inverse function such that (x·Inv(x,m)) mod m == 1?

part c) ... this question doesn't need to be reworded. You can assume that the inverse function works without having to determine how to implement it.

 

[rcgldr]

Late update, but I wanted to preserve the restated questions and provide the answer in case a similar problem about finite field math appears later:

Suppose x and y are mutually prime and there exists two integers a and b such that
1 = a · x + b · y.

a) What does this tell us about a · x mod y and b · y mod x?

Spoiler

a is the inverse of x mod y
b is the inverse of y mod x
One of these will be negative. If a is negative, then the proper inverse for x mod y = a + y, if b is negative, then the proper inverse for y mod x = b + x

b) Can we use this to construct an inverse function inv(x,m) so that (x · inv(x ·m)) mod m = 1? What relationship is required between x and m?

Spoiler

At this point, the problem just states that the inverses exist, without explaining how to construct an inverse function. The extended Euclid algorithm can be used to determine inv(x,m), but that's beyond the scope of this problem. It's sufficient to state that an inverse function exists.

The required relationship between x and m is that they be mutually prime. Proving this is true is beyond the scope of the problem.

c) Suppose p and q are prime numbers. Define z = p · inv(p,q) · x + q · inv(q,p) · y. What is z mod p and what is z mod q?

Spoiler

p · a mod p = 0 for any a
q · b mod q = 0 for any b
(c · inv(c,m)) mod m = 1 for any c or m (if mutually prime)

z mod p = (p · inv(p,q) · x + q · inv(q,p) · y) mod p = (0 + 1 · y) mod p = y mod p
z mod q = (p · inv(p,q) · x + q · inv(q,p) · y) mod p = (1 · x + 0) mod q = x mod q