# How to prove that some number has a particular factor without dividing

Suppose that there is a natural number. One wants to show that the number has particular (natural number) factor, but without dividing the number by the "supposedly" factor.

How does one do this?

-

It depends on the tools on which you might have. Suppose we have natural number $n$ and we wish to show that $d$ divides $n$, without actually dividing. Then we could do any of the following:

1. Depending on whether or not you consider an application of the Division Algorithm as dividing, you may show that the remainder $r$ in $n = dq + r$ is $0$.
2. You may show that the greatest common divisor of $d$ and $n$ is $d$.
3. You may subtract $d$ from $n$ repeatedly until either you reach $0$, or reach some natural number that is less than $d$.
-

Let the natural number be $n$, let the factor be $d$. If you can find relatively prime integers $p,q$ such that $d=pq$, then you can show $n$ has the factor $d$ by dividing it by $p$ and and dividing it by $q$.

More generally, if you have numbers $a_1,\dots,a_r$ whose least common multiple is $d$ then you can test for divisibility by $d$ by testing individually for divisibility by each of the $a_i$.

-

One may use various Divisibility Tests e.g. casting out nines. Or one may recognize an integer factor as a special case of polynomial factor, e.g. $\rm\:x-y\:$ divides $\rm\:f(x)-f(y)\:$ for $\rm\:f\:$ a polynomial with integer coefficients, which for $\rm\:x=10,\ y = 1\:$ essentially yields casting out nines, and for $\rm\:f = x^k\:$ it yields the well-known fact that $\rm\:m-n\:$ divides $\rm\:m^k - n^k.$

Often number identities are more perceptively viewed as special cases of function or polynomial identities. For example, Aurifeuille, Le Lasseur and Lucas discovered so-called Aurifeuillian factorizations of cyclotomic polynomials $\rm\;\Phi_n(x) = C_n(x)^2 - n\ x\ D_n(x)^2\;$. These play a role in factoring numbers of the form $\rm\; b^n \pm 1\:$, cf. the Cunningham Project. Below are some simple examples of such factorizations (e.g. see below).

$$\begin{array}{rl} x^4 + 2^2 \quad=& (x^2 + 2x + 2)\;(x^2 - 2x + 2) \\\\ \frac{x^6 + 3^2}{x^2 + 3} \quad=& (x^2 + 3x + 3)\;(x^2 - 3x + 3) \\\\ \frac{x^{10} - 5^5}{x^2 - 5} \quad=& (x^4 + 5x^3 + 15x^2 + 25x + 25)\;(x^4 - 5x^3 + 15x^2 - 25x + 25) \\\\ \frac{x^{12} + 6^6}{x^4 + 36} \quad=& (x^4 + 6x^3 + 18x^2 + 36x + 36)\;(x^4 - 6x^3 + 18x^2 - 36x + 36) \\\\ \end{array}$$

-