# GCD of two very large numbers

Mathematics

Hard

#### Problem Statement (Simplified):

For given two large numbers `M` and `N`, find their `gcd(M,N)`.

`GCD(M,N)` is the larget number possible which divides both.

See original problem statement here

#### Test Case:

``````Input:
15 130

Output:
5

Explanation:
5 divides 15 and 130 both completely and there exists no number greater than 5 which divides both of them completely.``````

#### Solving Approach :

1) For provided numbers, we know `N` is of size less than or equal to `100`, so we would need to store this number in a string.

2) We know we get the remainder less than `N` always if we divide any number by `N`.

3) To get the remainder by dividing a number stored `String` by `Number`, we calculate the remainder digit by digit. We update the remainder at every digit until all string is iterated.

4) In each iteration, we take the digit and make it greater than our current remainder by multiplying it by 10 and adding it to digit, no we take `mod` of digit by `N` and store as our current remainder. After the whole string is iterated, we get our remainder.

5) After we divide `M` by `N` and extract it's remainder, now both of them are of in Long Integer range, and we can carry with our `Long Division Method` for getting `gcd(M`,N)` where `M is our new smaller number.

6) `Long Division Method`: We repeatedly store remainder i.e (`Larger number` % `Smaller number`) and update `Larger number` by `Smaller number` until `smaller number` completely divides the `larger number`. Last `Smaller Number` after all steps, is our `gcd`.

#### Example:

We'll be given with two nmubers out of which one is `string` and one is `long` number. Hence we go through programming languages online course and remainder of `string` number and `long` number.

We can dry run above mentioned techinque,let's say given numbers are `143254` and 3, so first we convert `143254` to `long` number which will be `143254` % `3`. We take mod=0, which will store our final value, So,

• For S[i] = 1
`mod = mod x 10 + S`
`mod = 0 x 10 + 1`
`mod = 1`
`mod = mod` % `n`
`mod = 1` % `3`
`mod = 1`

• For S[i] = 4
`mod = mod x 10 + S`
`mod = 1 x 10 + 4`
`mod = 10 + 4`
`mod = 14`
`mod = mod` % `n`
`mod = 14` % `3`
`mod = 2`

• For S[i] = 3
`mod = mod x 10 + S`
`mod = 2 x 10 + 3`
`mod = 20 + 3`
`mod = 23`
`mod = mod` % `n`
`mod = 23` % `3`
`mod = 2`

• For S[i] = 2
`mod = mod x 10 + S`
`mod = 2 x 10 + 2`
`mod = 20 + 2`
`mod = 22`
`mod = mod` % `n`
`mod = 22` % `3`
`mod = 1`

• For S[i] = 5
`mod = mod x 10 + S`
`mod = 1 x 10 + 5`
`mod = 10 + 5`
`mod = 15`
`mod = mod` % `n`
`mod = 15` % `3`
`mod = 0`

• For S[i] = 4
`mod = mod x 10 + S`
`mod = 0 x 10 + 4`
`mod = 4`
`mod = mod` % `n`
`mod = 4` % `3`
`mod = 1`

As we have got our values in integer form, we can now use long division method, to find out gcd of both number that is `gcd(n,mod)`.

Let's take 25 and 135 for example, we find `gcd` of both using `Long Division Method`. As soon as our `remainder` becomes `0`, `dividend` is our `gcd(a,b)`.

#### Solutions:

```#include <stdio.h>
#include<string.h>

long long modBigNumber(char num[], long long m)
{
long long mod = 0;

for (int i = 0; i < strlen(num); i++) {

int digit = num[i] - '0';

mod = mod * 10 + digit;

mod = mod % m;
}

return mod;
}

int main()
{
int test;
scanf("%d",&test);
while(test--){

long long small;
long long largeF;
char large;

scanf("%lld%s",&small,large);
largeF = modBigNumber(large,small);

if(largeF==0){
printf("%lld\n",small);
}
else{
int temp = small;
small = largeF;
largeF = temp;

while(1){
if(largeF%small==0){
printf("%lld\n",small);
break;
}
int temp = small;
small = largeF%small;
largeF = temp;
}
}
}
}
```
```#include <bits/stdc++.h>
using namespace std;

long long modBigNumber(string num, long long m)
{
long long mod = 0;

for (int i = 0; i < num.size(); i++) {

int digit = num[i] - '0';

mod = mod * 10 + digit;

mod = mod % m;
}

return mod;
}

int main()
{
int test;
cin>>test;

while(test--){

long long small;
long long largeF;
string large;

cin>>small>>large;
largeF = modBigNumber(large,small);

if(largeF==0){
cout<<small<<endl;
}
else{
int temp = small;
small = largeF;
largeF = temp;

while(true){
if(largeF%small==0){
cout<<small<<endl;
break;
}
int temp = small;
small = largeF%small;
largeF = temp;
}
}
}
}
```
```import java.util.*;
import java.io.*;

public class Main {

static long modBigNumber(String num, long m){
long mod = 0;

for (int i = 0; i < num.length(); i++) {

int digit = num.charAt(i) - '0';

mod = mod * 10 + digit;

mod = mod % m;
}

return mod;
}

public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();

while(test!=0){

long small = sc.nextLong();
long largeF;
String large = sc.next();

largeF = modBigNumber(large,small);

if(largeF==0){
System.out.println(small);
}
else{
long temp = small;
small = largeF;
largeF = temp;

while(true){
if(largeF%small==0){
System.out.println(small);
break;
}
temp = small;
small = largeF%small;
largeF = temp;
}
}
test--;
}
}
}
```