# Problem

Problem Link – UVa 10407 – Simple division

Given an array of numbers, find the largest number $d$ such that, when elements of the array are divided by $d$, they leave the same remainder

# Solution

We will be using our knowledge about Congruence Relation and GCD to solve this problem. But first, we need to make sure that we understand the problem properly.

## Wrong Approach

At first, one might think that $d$ is the $gcd$ of array elements. Surely, dividing elements of the array with $d$ will leave same remainder $0$, but that doesn’t necessarily mean it is the largest possible answer.

For example, suppose the array is $A = {2,8,14,26}$. Then what will be the $gcd$ of array A? $gcd(2,8,14,26) = 2$. Dividing elements of $A$ with $2$ leaves us $0$. So is this our answer? No.

For array $A$, there exists a number greater than $2$ that leaves the same remainder. And that number is $3$. When we divide each element with $3$, it leaves us $2$ as the remainder.

The problem did not ask us to find the number that will leave $0$ as remainder. It asked us to find the largest number $d$ that leaves the same remainder. So for array $A$ the $gcd(A)$ is not the answer. Is $3$ our answer? No. The answer is given below in Example.

## Using Congruence Relation

Let us rephrase the problem using congruence relation. Suppose there is an array with elements, $A={a,b,c}$. We need to find the largest number $d$ that leaves the same remainder for each of its element.

Let us consider only ${a,b}$ for now. We need to find $d$ such that it leaves the same remainder when it divides $a$ and $b$. Meaning

$$a \ \equiv \ b \ \text{(mod d)} \ a – b \ \equiv \ 0 \ \text{(mod d)}$$

What does this mean? It means, if $d$ leaves the same remainder when it divides $a$ and $b$, then it will leave no remainder when dividing $a-b$.

Using same logic, we can say that $b – c \ \equiv \ 0 \ \text{(mod d)}$. Therefore, if we find a number that divides $a-b$ and $b-c$, then that number will leave the same remainder when dividing ${a,b,c}$.

This idea can be extended for any number of elements in the array. So $d$ is such a number that leaves no remainder when it divides the difference of adjacent elements in the array.

But wait, there are multiple numbers that can divide the difference of adjacent elements. Which one should we take? Since we want the largest value of $d$, we will take the largest divisor that can divide all the difference of adjacent numbers. There is only one divisor that can divide all the adjacent differences, and that is $gcd( (a-b), (b-c) )$.

Therefore, if we have an array $A={a_1,a_2,a_3…a_n}$, then $d = gcd( a_2 – a_1, a_3- a_2,…a_n – a_{n_1})$.

Careful about negative value of $gcd()$. Make sure you take the absolute value of $gcd()$.

# Example

Let us get back to the example we were looking into before. Finding $d$ for the array $A = {2,8,14,26}$. We know that $d$ will divide the difference of adjacent elements completely. So let us make another array that will contain the difference of adjacent elements., $B = {8-2, 14-8, 26-14} = {6,6,12}$. Therefore, $d = gcd ( 6,6,12 ) = 6$.

# Summary

• Let the array of elements be $A = {a,b,c,d…}$.
• $res \neq gcd(a,b,c,d…)$.
• $res = gcd ( a-b,b-c,c-d,…)$.

# Code

#include <bits/stdc++.h>
using namespace std;

typedef long long vlong;

vlong gcd ( vlong a, vlong b ) {
while ( b ) {
a = a % b;
swap ( a, b );
}
return a;
}

vlong arr[1010];

int main () {

while ( scanf ( "%d", &arr[0] ) != EOF ) {
if ( arr[0] == 0 ) break; // End of test case

// A new test case has started
int cur = 1;

// Take input
while ( 1 ) {
scanf ( "%lld", &arr[cur] );
if ( arr[cur] == 0 ) break;
else cur++;
}

vlong g = 0; // Start with 0 since gcd(0,x) = x.
for ( int i = 1; i < cur; i++ ) {
int dif = arr[i] - arr[i-1]; // Calculate difference
g = gcd ( g, dif ); // Find gcd() of differences
}

if ( g < 0 ) g *= -1; // In case gcd() comes out negative
printf ( "%lld\n", g );
}

return 0;
}


# Problem

Problem Link – UVa 11388 – GCD LCM

Given two positive integers $(G, L)$, we have to find a pair of integers $(a,b)$ such that $gcd(a, b)=G$ and $\text{lcm}(a, b)=L$. If there are multiple such pairs, we have to find the pair where $a$ is minimum. Also, both $a$ and $b$ needs to be positive.

# Solution

We don’t know the value of $(a,b)$ yet. Here is how I approached the problem.

## Value of $a$

What we know that $gcd(a,b) = G$. So, $G$ divides $a$ and $b$. Therefore, $a$ is a multiple of $G$. We also need to make sure that $a$ is as small as possible. So, what is the smallest positive number that can be divided by $G$? The answer is $G$ itself.
$$\therefore a = G$$

## Existence of Solution

Next, we know that $lcm(a,b)$ is the smallest positive number which is divisible by both $a$ and $b$. Since $a=G$ and $a \ | \ lcm(a,b)$, it follows that $a = G$ should divide $lcm(a,b) = L$. If $L$ is not divisible by $G$, then no solution exists.

$$\therefore \text{if } (G \not | L), \text{no solution exists}$$

## Value of $b$

The value of $b$ can be derived in the following way. We know that:

$gcd(a,b) \times lcm(a,b) = a \times b$
$G \times L = G \times b$
$b = \frac{G \times L}{G}$
$\therefore b = L$.

# Summary

1. $a = G$
2. If $G \not | L$, no solution exists
3. $b = L$
4. $\therefore (a,b) = (G,L)$

# Code

Here is the code in C++

#include <bits/stdc++.h>

int main () {
int kase;
scanf ( "%d", &kase ); // Input number of case

while ( kase-- ) {
int G, L;
scanf ( "%d %d", &G, &L ); // Take input

int a, b; // Need to find their value

a = G;

if ( L % G != 0 ) {
printf ( "-1\n" ); // No Solution
continue;
}

b = L;

printf ( "%d %d\n", a, b );
}

return 0;
}