# Modulus Problem

#### joshuaa

Choose three integer numbers x, y, and z = c, respectively, where x>=1, y>=1, and z >=1 to get (a, b) pairs. The condition is (1<=a<=x, 1<=b<=y) where [ (a + b) % c = 0 ] , a and b are integer numbers.

Note: % is modulus

For example: x = 10, y = 5, z = 2

I will show a few pairs, (1,1), (1,3), (5,1), (7,3)…..etc

I got the answer using two loops in java programming language. This way is not effective when you use large numbers. It takes a lot of time to get the answer. Therefore, I tried to create a formula.

I discovered that when I do this xy / z, I get an approximate answer for large numbers while most of the time I get same answer for small numbers.

For example: x = 70001, y = 6022, z = 316
xy / z = (70001)(6022)/(316) = 1334006 but the correct answer = 1333997 exact pairs

Is there another formula that gives me exact pairs?

Last edited:

#### Idea

Try this. I don't know if this formula can be simplified or whether this is an efficient way of solving the problem

$$\displaystyle \sum _{a=1}^x \left(\left\lfloor \frac{a+y}{z}\right\rfloor -\left\lceil \frac{a+1}{z}\right\rceil +1\right)$$

• joshuaa

#### joshuaa

for x = 10, y = 5, and z = 2, the formula give 30, but the answer is 25

#### Idea

for x = 10, y = 5, and z = 2, the formula give 30, but the answer is 25
the formula gives 25
it involves the floor and the ceiling functions

• joshuaa

#### joshuaa

wOW man. your formula is working perfectly so far, even for large numbers. Its speed is also fabulous. How did you attack the problem to create that magic formula?

at first I have not noticed the floor and the ceiling, but later wOW MAGIC!

#### joshuaa

I am sorry to tell you this, I want to implement this function for very large numbers up to 10^18, so it will take some time to get the summation. Do you think that there is a way to solve this formula to get rid of the summation (sigma) part?

I need something similar to this: the summation of n = n(n+1)/2

By, the way, what you have done to create this formula is very smart!

#### Idea

Another approach.
Consider the following union of intersections of intervals

$$\displaystyle S=\underset{k=1}{\overset{m}{\cup }}([1,x]\cap [k z-y,k z-1])$$

where

$$\displaystyle m= \left\lfloor \frac{x+y}{z}\right\rfloor$$

Each element $a\in S$ will produce a solution in the form $(a,k z-a)$
therefore the number of solutions equals card $S$

If $m$ is not too big this might actually work

• joshuaa

#### joshuaa

How can I apply this for x = 5, y = 10, z = 8? the answer is should be 5 pairs

let me try

m = 1
S = [1,5] intersecton [-2, 7]

then what?

#### Idea

How can I apply this for x = 5, y = 10, z = 8? the answer is should be 5 pairs

let me try

m = 1
S = [1,5] intersecton [-2, 7]

then what?
that gives $S=[1,5]= \{1,2,3,4,5\}$ . An interval here is just a set of natural numbers

so we have $k=1$ and $a=1,2,3,4,5$

since $z=8$ we get $b = z - a = 7,6,5,4,3$

5 pairs: $(1,7),(2,6),(3,5),(4,4),(5,3)$

• topsquark

#### joshuaa

wOW. that’s beautiful! is k always = 1? What about y = 10, we did not use it!!