# Factor 90301 without the aid of the computer

Computer break down easily know $90301=73\cdot1237$ Is there any way I want, without the aid of the computer to determine 90301 is a prime number or Composite number

-
My guess is no. It could potentially be divisible by any prime less than 300. – Mike Apr 27 '12 at 8:11
By computer, the fastest way to factor integers of less then 100 digits is the Quadratic Sieve. By hand, it is still really fast, but it is rather complicated. If you know the algorithm inside out, you could factor an integer this large without any prior knowledge in as a little as a couple of minutes. See: en.wikipedia.org/wiki/Quadratic_sieve – Eric Naslund Apr 27 '12 at 8:13
Maybe there is a Divisiblity rule for that, but unfortunately it's not listed here... Does any body know? – draks ... Apr 27 '12 at 8:33
Well, if you only want to know it is prime or not and if you can afford some error, you can use Fermat primality test. See this wikipedia article: en.wikipedia.org/wiki/Fermat_primality_test – FiniteA Apr 27 '12 at 8:33
Showing that a number is composite (as asked for in the body of your question) is often easier than factoring the number (which is the question in your subject.) Do you really want to factor it, or just show that it isn't prime? – Thomas Andrews Apr 27 '12 at 13:14

Since $90301=300^2+300+1$, to check if a prime $p$ divides $90301$ you can compute $q=300\mod p$ (the remainder of the division of $300$ by $p$) and check if $q^2+q+1$ is divisibe by $p$. You still have to try all primes below $300$, but the computations are somewhat easier.

For instance let $p=13$. Then $300=23\cdot 13 +1$, so that $q=1$. Since $13$ does not divide $q^2+q+1=3$, it does not divide $90301$. Observe that the same computation shows that $23$ does not divide $90301$.

-

Use the fact that $73\times 137 = 10001$. This gives you a divisibility test for 73 and 137, similar to the ones for 7 and 13, but with groups of 4 digits instead of 3. Or simply notice that you can subtract 10001, divide by 10, and be left with 803; which is obviously divisible by 73.

-
And how do you guess that $73$ is a factor in you don't know it beforehand and can't use a computer? – Mikko Korhonen Apr 27 '12 at 13:23
For these problems, you try primes till you find one that's divisible. Start with 2, then 3, then 5 and so on. Some small primes have easy divisibility tests; many don't. But eventually, you'll get to 73. When that happens, this is the test that you use. – user22805 Apr 27 '12 at 20:35

With a little insight and with a little luck we can find the smallest prime factor quite easily.

Suppose prime $\rm\:p\ |\ 90301 = a^2+a+1 = (a^3-1)/(a-1),\:$ for $\rm\:a = 300.\:$ Therefore, $\rm\:mod\ p\!:\ a^3\equiv 1,\:$ so if $\rm\:a\not\equiv 1\:$ then $\rm\:a\:$ has order $3,$ so $\rm\:3\ |\ p-1.\:$ But $\rm\:a\equiv 1\:\Rightarrow\:p\ |\ 3\nmid 90301.$

So every prime divisor of $90301$ is $\equiv 1\pmod 3.\:$ We might deduce stronger divisor congruences if $\rm\:a\:$ is a power, e.g. $\rm\:a \equiv c^2\:$ $\Rightarrow$ $\rm\:c^{6}\equiv 1,\:$ so if $\rm\:c^3\not\equiv 1\:$ then $\rm\:c\:$ has order $6,\:$ so $\rm\:6\ |\ p-1.\:$ Similarly $\rm\:a\equiv c^3\:$ $\Rightarrow$ $\rm\:c^{9}\equiv 1,\:$ so if $\rm\:c^3\not\equiv 1\:$ then $\rm\:c\:$ has order $9,\:$ so $\rm\:9\ |\ p-1.\:$

The first case $\rm\:a\equiv c^2\:$ doesn't yield easy solutions but the second case $\rm\:a\equiv c^3\:$ strikes gold quickly. We seek primes $\rm p$ such that $\rm\: a = 300 \equiv c^3,\:$ i.e. $\rm\:p\ |\ 300- c^3.\:$ For $\rm\:c=1\!:\ 300-1^2 = 13\cdot 23\:$ but neither factor is $\equiv 1\pmod 9.\:$ For $\rm\:c=2\!:\ 300-2^3 = 4\cdot 73\:$ and $\:73\equiv 1\pmod 9$ and this works: $\: 73\ |\ 90301.$

Note $\$ Often properties of numbers are specializations of those of functions (e.g. polynomials), as above where integer factorizations arise by specializing factorizations of cyclotomic polynomials. Here are some other useful examples. Aurifeuille, Le Lasseur and Lucas discovered the 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:

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

-

The only primality test I know to do by hand is the following:

• $n$ is prime if non of the primes $p\leq \sqrt{n}$ divides $n$.

In your case you'll have to check all the primes below $300$.

-