Problem 8

• #	mod5	mod7
  0	0	0
  1	1	1
  2	2	2
  3	3	3
  4	4	4
  5	0	5
  6	1	6
  7	2	0
  8	3	1
  9	4	2
  10	0	3
  11	1	4
  12	2	5
  13	3	6
  14	4	0
  15	0	1
  16	1	2
  17	2	3
  18	3	4
  19	4	5
  20	0	6
  21	1	0
  22	2	1
  23	3	2
  24	4	3
  25	0	4
  26	1	5
  27	2	6
  28	3	0
  29	4	1
  30	0	2
  31	1	3
  32	2	4
  33	3	5
  34	4	6
  35	0	0
  36	1	1

• For this to be true, \(x\) and \(y\) must be relatively prime. From this, we can observe a pattern that forms where there are unique pairs for (x,y) until the \(x*yth\) pair (or index). In our example, \(x=5\), \(y=7\), and it will have unique pairs until the pattern repeats on the \(35th\) index (which is x*y).

• Since x and y are prime the \(gcd(x,y) = 1\).

  Using Bezout’s identity we know \(y(y^{-1}modx) + x(x^{-1}mody)=1\)

  Then you can multiply both sides by \(q\).

  \(qy(y^{-1}modx) + qx(x^{-1}mody)=q\)

  Now if you \(modx\) both sides, you get:

  \(qy(y^{-1}modx)modx + qx(x^{-1}mody)modx=qmodx\)

  so

  \(qy(y^{-1}modx)modx = 1*q\)

  \(qx(x^{-1}mody)modx = 0\)

  Therefore: \(qy(y^{-1}modx)modx + qx(x^{-1}mody)modx = qmodx = m\)

  The coefficient for the \(y(y^{-1}modx)\) term is \(m\). Then if you take \(mody\) of the function, you get:

  \(qy(y^{-1}modx)mody + qx(x^{-1}mody)mody = qmody = n\).

  So the coefficient of the \(x(x^{-1}mody)\) term is \(n\).

  Then we have \(my(y^{-1}modx) + nx(x^{-1}mody) = q\). But Bezout’s identity says this will only work for specific \(y^{-1}modx\) and \(x^{-1}mody\). So to get this formula to work for all \(y^{-1}modx\) and \(x^{-1}mody\) we need to add a \(modxy\) term.

  So the final formula is \(q=[my(y^{-1}modx) + nx(x^{-1}mody)]modxy\)

• In the case where there are three primes \(x,y,z\), the properties from above still hold. There will be unique pairs until the \(x*y*zth\) index.