Divisibility by prime numbers

Suppose prime number $p$ and an arbitrary number $r$ is given. What methods do you know for detection that $r$ is divisible by $p$?

-
So you try to divide $r$ by $p$ ... ? – Thomas Oct 7 '12 at 21:13
@Thomas and you have to check whether what you got is an algebraic integer, if you're not in $\mathbb Q$ but in some larger algebraic field. But it's not clear if this is what Wreza asks for... – yo' Oct 7 '12 at 21:19
@tohecz: ahh ok, I was thinking that something deeper was going on. – Thomas Oct 7 '12 at 21:20
So lets say that I am wondering if $11313559|45254236$. Method: wolframalpha.com/input/?i=factor+45254236 . Answer: yes – P.. Oct 7 '12 at 21:24
But as I say, I'm not sure whether this is what is asked. If so, it is not an easy task: You easily get some polynomial with root $r/p$ if you know minimal polynomials of $p$ and $r$, but you need to find the minimal one for $r/p$ which is a complicated task. – yo' Oct 7 '12 at 21:26

The best way that's known for doing this is also the most straightforward way: You have to divide and check. How do you do that? I'll give you two answers: One for if you're a human, and one for if you're a computer.

If you're a human:

Chances are, the numbers are represented in base 10. In this base, for certain values of $p$, there are certain "tricks" you can use to speed up the division. For example, dividing a number by 2 or 5 reduces to checking its least significant digit (and it is no coincidence that these are the factors of 10). Dividing by 3 or 9 can be done by summing the digits of $r$ and checking the divisibility of the sum. And there are more rules. Unfortunately, this cannot really (easily) be generalized for larger values of $p$, and you'll end up just having to do long division (or another division algorithm that humans can do - I don't personally know one).

If you're a computer:

We are given two integers, $a$ and $b$ (it turns out we don't care whether $b$ is prime - that's why I changed the letters...) and we want to check whether $a$ is divisible by $b$.

The "naïve" algorithm is simple: Try dividing $a$ by $b$, and see whether you get an integer.

How does a computer divide two numbers? A simple way to do this would be to use "long division" (or "pen-and-paper division"), which is exactly how you learned to divide in elementary school. (The difference is that since you're a computer, you'll probably work in base 2, base 16, base 256 or some other base which is a power of 2, instead of the "human" base 10. Any computer would agree this is much easier and faster!)

Let's try to analyze how fast this algorithm is, at least in terms of complexity. If this term is new to you, it means something like this: If we graph the speed of the long division algorithm as a function of how many digits there are in the input, what sort of graph do we get? Linear? Logarithmic? Quadratic?

Denote by $d_1$ the number of digits in $a$, and by $d_2$ the number of digits in $b$ (these are actually the logarithms of $a$ and $b$, rounded, taken in the base that the numbers are represented in). Now, recall how long division works:

1. At each step, we look at $d_2$ digits (give or take 1) of $a$, and divide the number made up of those digits by $b$. This "smaller" division step can be done by subtracting $b$ repeatedly until we get a value smaller than $b$, and that's our remainder from this "small" step. The amount of subtractions we need to do is no more than a constant (for example no more than 10 if we work in base 10), so this step has time complexity $O(d_2)$ (the time each subtraction takes). If you're unfamiliar with this notation, it means "no more than $d_2$ multiplied by some constant inherent in the algorithm which we don't care to specify".

2. The amount of such "small divisions" we need to perform is equal to $d_1$ (give or take up to $d_2$), as we move "further down" the number $a$.

So, this simple algorithm's running time is $O(d_1 d_2)$. This is certainly not the fastest or most suitable way to do this (take a look at this Wikipedia article for a survey of some faster methods), but it's not too shabby! For instance, you can check a number $a \approx 2^{1024}$ for divisibility by a number $b \approx 2^{512}$ in about half a million steps, which is very fast in modern standards.

How much this can be improved turns out to be a pretty difficult question. If this interests you, I suggest you look at this Wikipedia article: There are 6 different non-trivial multiplication algorithms listed there, and the "Newton-Raphson division" method allows you to "convert" any multiplication algorithm to a division algorithm running at the same speed.

One thing's for sure: No division algorithm will be strictly faster than $O(d_1 + d_2)$. The reason is that this is the time complexity of just reading the digits, and you can't divide correctly without knowing all the digits. So the "game" of optimizing division is between $O(d_1 + d_2)$ and $O(d_1 d_2)$.

-
Thaks my friend ,but I wan't more algorithms, do you know another ones? – Wreza Shafaghi Oct 8 '12 at 6:22
Sure - I wrote about it briefly in the paragraph before last. You can also find a survey in the Wikipedia article for "division algorithm". – Yoni Rozenshein Oct 8 '12 at 13:33

I'll show you with an example:

Check that 311 is prime

The square root of 311 is roughly 17 (prime).

Check if the primes starting at 2 and leading up to 17 divide evenly into 311. None do. Therefore, 311 is a prime number.

Yay!

-
Please read the question again. This is not what was asked for. (And it seems unnecessary to bump a question that's almost a year old for this.) – mrf Jul 21 '13 at 15:48