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