check for a number is divisible or not

Question

I have a very very large integer (but it's form is specific), how can i test if this integer is divisible or not (primality check)
number = 1(68 times 0)9(6 times 0)21(66 times 0)189

for instance: 1(3 times 0)4 is 10004

Answer 1

Fermat's theorem says that if $p$ is a prime, then for all integers $a$ we have $a^p \equiv a \pmod{p}$. An equivalent formulation is that if $a$ is not a multiple of $p$, then $a^{p-1} \equiv 1 \pmod{p}$. That - and variants of that - is the basis of many fast probabilistic primality tests (compositeness tests, more accurately).

If we want to know whether an odd number $n > 1$ is prime (even $n$ are trivial), then we can check whether Fermat's property holds, that is, compute the remainder of $a^{n-1}$ modulo $n$ for some $a$ which is not a multiple of $n$. If we find

$$a^{n-1} \not\equiv 1 \pmod{n},$$

then we know that $n$ is composite - we have no idea what the factors may be, but we know it's composite.

If on the other hand we find $a^{n-1} \equiv 1 \pmod{n}$, and that's not trivially satisfied, as it would be for $a \equiv \pm 1 \pmod{p}$, then we don't know that $n$ is prime, there are composite numbers $n$ where $a^{n-1} \equiv 1 \pmod{n}$ holds for a lot of $1 < a < n-1$, but that is a comparatively rare occurrence, and so $n$ is probably prime, $n$ is a base-$a$ (Fermat) probable prime. If $n$ is in fact composite, $n$ is a base-$a$ (Fermat) pseudoprime.

Fermat pseudoprimes to any given base are rare, much rarer than primes (there are only $245$ base-$2$ Fermat pseudoprimes less than one million, while there are $78498$ primes less than one million), so that is a rather good test. It becomes better if we test several different bases, then the probability of a composite number passing the test becomes smaller (there are only $66$ Fermat pseudoprimes for both bases, $2$ and $3$, below one million, and only $36$ for the three bases $2,\,3$ and $5$). However, there are composite numbers - Carmichael numbers - such that you have $a^{n-1} \equiv 1 \pmod{n}$ for all $a$ that are coprime to $n$. For such numbers, the probability of passing the Fermat test is uncomfortably high.

But we can make the test stronger in a different way. For an odd $n > 1$, write $n-1 = 2^s\cdot m$ with $m$ odd. Then we can factor

$$a^{n-1}-1 = a^{2^sm}-1 = \left(a^{2^{s-1}m}+1\right)\left(a^{2^{s-2}m}+1\right)\dotsb\left(a^{m}+1\right)\left(a^m - 1\right).\tag{1}$$

These factors cannot have any common prime factor except $2$, so if $n$ is prime, then $n$ divides exactly one of these factors (since it divides the left hand side). If $n$ is composite and $n$ divides the left hand side (that is, if $n$ is a base-$a$ Fermat pseudoprime), then it is likely that different prime factors of $n$ will divide different factors of the right hand side of $(1)$.

That gives the strong base-$a$ Fermat test, if an odd $n > 1$ divides one factor of the right hand side of $(1)$, then $n$ is a strong base-$a$ (Fermat) probable prime. If such an $n$ is in fact composite, it is a strong base-$a$ (Fermat) pseudoprime.

Strong Fermat pseudoprimes are much rarer than ordinary pseudoprimes, up to one million, there are only $46$ strong base-$2$ pseudoprimes, and none that is a strong pseudoprime for the two bases $2$ and $3$.

So a fairly indicative test is a strong Fermat test for several bases. If the bases are (pseudo-)randomly chosen, that is the Miller-Rabin primality test.

In the case of the given number, the ordinary Fermat test for base $2$ already reveals the compositeness of the number.

Answer 2

I recommend that you use the Miller–Rabin primality test. There are many implementations available online. Since the number you gave is really large, using the "traditional" algorithm $\mathcal{O}(\sqrt{n})$ is not fast enough.