# What is the biggest computation one should use for an induction base

First of all sorry for me (informal) language here - i am not a native english speaker. I have tried to look up my question here but couldnt find anything. I also tried to look it up on google but i think its due to my lack of using the right words for it. I would appreciate any editing on my question.

I was prooving that a really big number (which was about the size of $10^{4033}$) is not a prime, altough one could just simply use e.g. Wolfram Alpha to verify it by computing the remainder when it is divided by one of its factors.

In my proof i used mathematical induction to show that numbers of that form have two certain factors. In my induction base i realised it would end up being something like: $$111 \cdot91=10101$$ Which is true - and therefore i showed that my assumption holds for an $n \in \mathbb{N}$.

Normally my induction bases would end up being statements which would be easy to see. But this time one may need a calculator to verify if the statement above is true.

Now my question is: If i use mathematical induction for a proof - how "complicated" or "large" should my induction bases are? Should one be able to recognize the true statement without the use of a calculator e.g.? How do i know that the computation which has to be done is fair enough?

• Sometimes the base case in an induction argument is quite complicated. It doesn't matter how complicated it is, as long as you prove it. In your case, there is not much involved in verifying the base case. Someone could verify it using a pencil and paper in a matter of seconds. – kccu Jan 14 '16 at 15:59
• The famous computer-aided proof of the Four Colour Theorem can be thought of as an induction with thousands of difficult to verify base cases. – André Nicolas Jan 14 '16 at 16:10
• $$111 \cdot 91 =(101+10)(101-10)=101^2-10^2=(100+1)^2-100=100^2+2 \cdot 100+1-100=100^2+100+1=10101$$ no calculator – N. S. Jan 14 '16 at 16:11
• @N.S. it was just an example - and i just said one may need - i was interested in cases where the base is way more complex :) – K. Hoffmann Jan 14 '16 at 16:17