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
 A: 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$.
A: 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.
A: 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}$$
A: 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$.
