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
Factor 90301 without the aid of the computer
-
1Showing 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? – 2012-04-27
4 Answers
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.
-
0For 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. – 2012-04-27
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$.