Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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$.
share|improve this answer

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$.

share|improve this answer

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}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.