# Divisibility Testing

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?

Related Linear and Abstract Algebra News on Phys.org
Hurkyl
Staff Emeritus
Gold Member
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...

NateTG
Homework Helper
Originally posted by 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?
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.

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???

NateTG
Homework Helper
Arbitrary precision arithmetic is pretty straightforward.

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 !!!

NateTG
Homework Helper
Originally posted by 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 !!!
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?

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

void div(char *s1,char *s2,char *r,char *q)
{
char op1[SIZE],op2[SIZE],res[SIZE],factor[SIZE],x[SIZE],div[SIZE],z[SIZE];
int i,j,l1,l2,ok;
strcpy(op1,s1);
strcpy(op2,s2);
strcpy(res,"0");
strcpy(q,"0");
l1=strlen(op1);
l2=strlen(op2);
for(i=l1-l2;i>=0;--i)
{
strcpy(x,"1");
strcpy(div,"0");
for(j=1;j<=i;++j)
{
x[j]='0';
}
x[j]=0;
mul(op2,x,factor);
while(1)
{
ok=sub(op1,factor,z);
if(ok==-1)
{
strcpy(q,op1);
break;
}
else
{
strcpy(op1,z);