# Divisibility Testing

1. Dec 15, 2003

### Moni

We've seen divisibility testing for different numbers...for 2,3,4,5,7,11.......

But now I want to know is there any way to find divisbility with any prime number?

Suppose, how can I say 12783461236 is divisible with 97 or not?

2. Dec 15, 2003

### Hurkyl

Staff Emeritus
Yes, there exist divisibility tests of that type for any number (not just primes), but in general they probably take more effort to use than simply dividing it by hand. The divisibility by 7 test hints at the way things get complicated...

3. Dec 15, 2003

### NateTG

Like:
Take the last digit, multiply by 29, subtract from the rest, and see if the result is divisible by 97?

It's probably faster to just trial divide.

4. Dec 16, 2003

### Moni

Actually I want to build a computer program...which can take any arbitrary size of 2 integers can tell larger one is divisible by the smaller one!

Can you give any link to proceed on???

5. Dec 16, 2003

### NateTG

Arbitrary precision arithmetic is pretty straightforward.

6. Dec 16, 2003

### Moni

Yes! I know, but I am going to develop a program myself :)

The google results I've got so far are with traditional division method, there is no use of such type of divisibility testing....

I want to develop one with this feature, then it will be faster than others available with stright forward DIVISION !!!

7. Dec 16, 2003

### NateTG

Observation 1:

The number of operations that you need for a 'traditional' division approach is $$log_2 m * log_2 n$$ where $$m,n$$ are the numbers that you're using. That's really fast already. So fast that checking numbers with thousands of digits should not take very long.

Are you trying to do some sort of crypto stuff?

8. Dec 17, 2003

### Moni

I just want to program myself with the use of Divisibility testing...