Divisibility Testing for Prime Numbers

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

 

[Hurkyl]

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]

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.

 

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

 

[NateTG]

Arbitrary precision arithmetic is pretty straightforward.

Google on it for more information.

 

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

 

[NateTG]

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?

 

[Moni]

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

For traditional division I use:

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);
add(div,x,div);
}
}
add(res,div,res);
}
if(l1<l2) strcpy(q,s1);
strcpy(r,res);
}

It's not that crypto tech...just making math soft and learning algorithms :)