# Proving that a number is composite

I have proved that the number $10^{5}2^{17}+1$ is composite by showing that it is divisible by 3 , using remainders. I want an alternative proof.I am looking for a very elementary proof that does not mention remainders.

• Why not include your proof in the post itself, please? – amWhy Dec 17 '13 at 17:34
• What is more elementary than using remainders? – mathematics2x2life Dec 17 '13 at 17:35
• I have a hard time imagining a technique in number theory that is more elementary than modular arithmetic. Well, explicit computation, perhaps. – hmakholm left over Monica Dec 17 '13 at 17:35
• Well, we can do it in harder ways. Like start with $10^5 2^{17}=(99999\times 2^{17})+2^{17}$. – André Nicolas Dec 17 '13 at 17:37
• I have found it in a school textbook and in that section everything is proved without explicitly mentioning the divisor.I just guessed that it was 3. – Narek Margaryan Dec 17 '13 at 17:38

The most elementary way to show compositeness must be direct computation:

$$10^5 2^{17}+1 = 13.107.200.001 = 3 \times 4.369.066.667$$

so the number is composite.

Here is a way without mentioning remainders. Look at the factorization: $$10^5 2^{17} + 1 = 3 \cdot 7 \cdot 624152381$$ Using remainders is the most elementary way. As you have shown, it is easy to show that $3$ divides your number. It is also easy to show that $7$ divides your number, since $2^{17} \equiv 4 \pmod{7}$ and $10^5 \equiv 5 \pmod7$.

You can try Wilson's Theorem (for the fun of it and complicating things)

$p>1$ is prime $\iff (p-1)! \equiv -1 \pmod p$

Show that the RHS of the statement does not hold for $10^5*2^{17}+1$.

Computation is still the best and most efficient way of showing that $10^5*2^{17}+1$ is composite though. :)

Choose a number $a$ with $\gcd(a, n) = 1$.

Check, if $a^{n - 1} = 1 \pmod n$. If it is not the case, then $n$ must be composite, but you do not know any factor in this case. This is a result of Fermat's little theorem.

• Note, that n need not to be prime, if the equation holds, but you have a good chance in this case that n is prime. – Peter Dec 17 '13 at 17:54

$10^5 \pmod 3 = (1)^5 \pmod 3 = 1 \pmod 3$.

$2^{17} \pmod 3 = (-1)^{17} \pmod 3 = -1 \pmod 3$.

Thus, $10^5 \times 2^{17} \pmod 3 = 1 \times (-1) \pmod 3 = -1 \pmod 3$.

Now, $10^5 \times 2^{17} + 1 \pmod 3 = -1 + 1 \pmod 3 = 0 \pmod 3$.

$$10^{5}2^{17}+1=10^{5}2^{17}-2^{17}+2^{17}+1\\ =2^{17}(10^5-1)+2^{17}+1^{17}$$

Now $10^5-1$ is divisible by $10-1=9$ thus by $3$.

Also $2^{17}+1^{17}$ is divisible by $2+1=3$.