1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why not include your proof in the post itself, please? $\endgroup$ – amWhy Dec 17 '13 at 17:34
  • 3
    $\begingroup$ What is more elementary than using remainders? $\endgroup$ – mathematics2x2life Dec 17 '13 at 17:35
  • 1
    $\begingroup$ I have a hard time imagining a technique in number theory that is more elementary than modular arithmetic. Well, explicit computation, perhaps. $\endgroup$ – hmakholm left over Monica Dec 17 '13 at 17:35
  • $\begingroup$ Well, we can do it in harder ways. Like start with $10^5 2^{17}=(99999\times 2^{17})+2^{17}$. $\endgroup$ – André Nicolas Dec 17 '13 at 17:37
  • $\begingroup$ 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. $\endgroup$ – Narek Margaryan Dec 17 '13 at 17:38
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peter Dec 17 '13 at 17:54
2
$\begingroup$

$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$.

$\endgroup$
1
$\begingroup$

$$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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.