# Check if any large number is divisible by 17 or not

Given a number, the task is to quickly check if the number is divisible by 17 or not. **Example:**

Input : x = 34 Output : Yes Input : x = 47 Output : No

A solution to the problem is to extract the last digit and subtract 5 times of the last digit from the remaining number and repeat this process until a two-digit number is obtained. If the obtained two-digit number is divisible by 17, then the given number is divisible by 17.**Approach:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

- Extract the last digit of the number/truncated number every time
- Subtract 5*(last digit of the previous number) from the truncated number
- Repeat the above three steps as long as necessary.

**Illustration:**

3978-->397-5*8=357-->35-5*7=0. So 3978 is divisible by 17.

Mathematical Proof :

Let be any number such that =100a+10b+c .

Now assume that is divisible by 17. Then

0 (mod 17)

100a+10b+c0 (mod 17)

10(10a+b)+c0 (mod 17)

10+c0 (mod 17)

Now that we have separated the last digit from the number, we have to find a way to use it.

Make the coefficient of 1.

In other words, we have to find an integer such that n such that 10n1 mod 17.

It can be observed that the smallest n which satisfies this property is -5 as -501 mod 17.

Now we can multiply the original equation 10+c0 (mod 17)

by -5 and simplify it:

-50-5c0 (mod 17)

-5c0 (mod 17)

We have found out that if 0 (mod 17) then,

-5c0 (mod 17).

In other words, to check if a 3-digit number is divisible by 17,

we can just remove the last digit, multiply it by 5,

and then subtract it from the rest of the two digits.

**Program :**

## C++

`// CPP Program to validate the above logic` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to check if the` `// number is divisible by 17 or not` `bool` `isDivisible(` `long` `long` `int` `n)` `{` ` ` `while` `(n / 100)` ` ` `{` ` ` `// Extracting the last digit` ` ` `int` `d = n % 10;` ` ` `// Truncating the number` ` ` `n /= 10;` ` ` `// Subtracting the five times the` ` ` `// last digit from the remaining number` ` ` `n -= d * 5;` ` ` `}` ` ` `// Return n is divisible by 17` ` ` `return` `(n % 17 == 0);` `}` `// Driver code` `int` `main()` `{` ` ` `long` `long` `int` `n = 19877658;` ` ` `if` `(isDivisible(n))` ` ` `cout << ` `"Yes"` `<< endl;` ` ` `else` ` ` `cout << ` `"No"` `<< endl;` ` ` `return` `0;` `}` |

## Java

`// Java Program to validate the above logic` `import` `java.io.*;` `class` `GFG {` `// Function to check if the` `// number is divisible by 17 or not` ` ` `static` `boolean` `isDivisible(` `long` `n)` `{` ` ` `while` `(n / ` `100` `>` `0` `)` ` ` `{` ` ` `// Extracting the last digit` ` ` `long` `d = n % ` `10` `;` ` ` `// Truncating the number` ` ` `n /= ` `10` `;` ` ` `// Subtracting the five times the` ` ` `// last digit from the remaining number` ` ` `n -= d * ` `5` `;` ` ` `}` ` ` `// Return n is divisible by 17` ` ` `return` `(n % ` `17` `== ` `0` `);` `}` `// Driver code` ` ` `public` `static` `void` `main (String[] args) {` ` ` `long` `n = ` `19877658` `;` ` ` `if` `(isDivisible(n))` ` ` `System.out.println( ` `"Yes"` `);` ` ` `else` ` ` `System.out.println( ` `"No"` `);` ` ` `}` `}` `// This code is contributed by inder_verma.` |

## Python 3

`# Python 3 Program to validate` `# the above logic` `# Function to check if the` `# number is divisible by 17 or not` `def` `isDivisible(n) :` ` ` `while` `(n ` `/` `/` `100` `) :` ` ` `# Extracting the last digit` ` ` `d ` `=` `n ` `%` `10` ` ` `# Truncating the number` ` ` `n ` `/` `/` `=` `10` ` ` `# Subtracting the five times ` ` ` `# the last digit from the` ` ` `# remaining number` ` ` `n ` `-` `=` `d ` `*` `5` ` ` `# Return n is divisible by 17` ` ` `return` `(n ` `%` `17` `=` `=` `0` `)` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `n ` `=` `19877658` ` ` ` ` `if` `isDivisible(n) :` ` ` `print` `(` `"Yes"` `)` ` ` `else` `:` ` ` `print` `(` `"No"` `)` `# This code is contributed` `# by ANKITRAI1` |

## C#

`// C# Program to validate the above logic` ` ` `using` `System;` ` ` `class` `GFG {` ` ` ` ` `// Function to check if the` `// number is divisible by 17 or not` ` ` `static` `bool` `isDivisible(` `long` `n)` `{` ` ` ` ` `while` `(n / 100>0)` ` ` `{` ` ` `// Extracting the last digit` ` ` `long` `d = n % 10;` ` ` ` ` `// Truncating the number` ` ` `n /= 10;` ` ` ` ` `// Subtracting the five times the` ` ` `// last digit from the remaining number` ` ` `n -= d * 5;` ` ` `}` ` ` ` ` `// Return n is divisible by 17` ` ` `return` `(n % 17 == 0);` `}` ` ` `// Driver code` ` ` ` ` `public` `static` `void` `Main () {` ` ` `long` `n = 19877658;` ` ` `if` `(isDivisible(n))` ` ` `Console.Write( ` `"Yes"` `);` ` ` `else` ` ` `Console.Write( ` `"No"` `);` ` ` `}` `}` |

## PHP

`<?php` `// PHP Program to validate the above logic` `// Function to check if the` `// number is divisible by 17 or not` `function` `isDivisible(` `$n` `)` `{` ` ` `while` `(` `$n` `/ 100 != 0)` ` ` `{` ` ` `// Extracting the last digit` ` ` `$d` `= (int)` `$n` `% 10;` ` ` `// Truncating the number` ` ` `$n` `/= 10;` ` ` `// Subtracting the five times` ` ` `// the last digit from the` ` ` `// remaining number` ` ` `$n` `-= ` `$d` `* 5;` ` ` `}` ` ` `// Return n is divisible by 17` ` ` `return` `(` `$n` `% 17 == 0);` `}` `// Driver code` `$n` `= 19877658;` `if` `(isDivisible(` `$n` `))` ` ` `print` `(` `"Yes"` `);` `else` ` ` `print` `(` `"No"` `);` `// This code is contributed by Raj` `?>` |

## Javascript

`<script>` `// JavaScript Program to validate the above logic` ` ` ` ` `// Function to check if the` `// number is divisible by 17 or not` ` ` `function` `isDivisible(n)` ` ` `{` ` ` `while` `(Math.floor(n / 100)>0)` ` ` `{` ` ` `// Extracting the last digit` ` ` `let d = n % 10;` ` ` ` ` `// Truncating the number` ` ` `n = Math.floor(n/10);` ` ` ` ` `// Subtracting the five times the` ` ` `// last digit from the remaining number` ` ` `n -= d * 5;` ` ` `}` ` ` ` ` `// Return n is divisible by 17` ` ` `return` `(n % 17 == 0);` ` ` `}` ` ` ` ` `// Driver code` ` ` `let n = 19877658;` ` ` `if` `(isDivisible(n))` ` ` `document.write( ` `"Yes"` `);` ` ` `else` ` ` `document.write( ` `"No"` `);` ` ` `// This code is contributed by avanitrachhadiya2155` `</script>` |

**Output:**

Yes

Note that the above program may not make a lot of sense as could simply do n % 23 to check for divisibility. The idea of this program is to validate the concept. Also, this might be an efficient approach if input number is large and given as string.