1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Question regarding modular arithmetic from discrete math

  1. Feb 10, 2013 #1
    1. The problem statement, all variables and given/known data


    2. Relevant 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.)

    3. The attempt at a solution

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

    Any hint regarding this subject would be really appreciated.
  2. jcsd
  3. Feb 10, 2013 #2


    User Avatar
    Homework Helper

    You can use attachments for images here at physics forums rather than using a photo web site 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 Zp refers to a set of integers modulo p.
  4. Feb 10, 2013 #3
    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
  5. Feb 10, 2013 #4


    User Avatar
    Homework Helper

    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.
  6. Feb 10, 2013 #5
    Sorry, I still don't quite understand how to solve the question, can you give me more hint?
  7. Feb 10, 2013 #6


    User Avatar
    Homework Helper

    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?
    Last edited: Feb 10, 2013
  8. Feb 12, 2013 #7


    User Avatar
    Homework Helper

    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 text book.

    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.
    Last edited: Feb 12, 2013
  9. Mar 9, 2013 #8


    User Avatar
    Homework Helper

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

    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?

    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
    Last edited: Mar 9, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted