4
$\begingroup$

I'm doing some exam practice questions and I am totally stuck on this one, been racking my brain for days without much progress. I would truly appreciate some help.

I tried so many different routes. But my tutor gave this following hint, but I am struggling to proceed with it, or really how it would even lead to a solution:

Start with the simplest example such that $10^n+3$ is composite with $n$ divisible by a small prime factor. I see that:

$10^4\equiv -3 (mod \space 7)$ (2 being the small prime factor obviously) or

$10^9\equiv -3 (mod \space 23)$ (with 3 as a small prime factor)

Then he said, prove that for all $n$ > some number, that it is divisible by this small prime factor.

So using the case for $n=9$, letting $n = 3k$ for some integer $k$, I re-write this as:

$(10^{3})^k\equiv -3 (mod \space 23)$

I know $10^3\equiv -3 (mod 17)$, but I am not sure how to proceed?

I'm usually pretty good with at least going in a reasonable direction with a hint, but I am truly stuck here.

Sincere thanks in advance.

$\endgroup$
6
  • $\begingroup$ When you look at $10^n$ mod $7$, you should be thinking about $7$ as the small prime factor (possibly dividing $10^n + 3$). $\endgroup$ – hardmath Oct 14 '13 at 10:36
  • $\begingroup$ I did think of that, but I see that for example $7 \nmid 10^7+3$, which is composite. $\endgroup$ – JackReacher Oct 14 '13 at 10:43
  • 1
    $\begingroup$ You aren't trying to show $7$ divides every number $10^n + 3$. Try to identify the pattern of which of these numbers is divisible by $7$ and then prove your guess (hint: Fermat's Little Thm.). $\endgroup$ – hardmath Oct 14 '13 at 10:50
  • $\begingroup$ Many thanks! I think I got it - from $n = 10$ onwards, I notice the pattern involves $10+6i$, applying FLT it becomes clear. Your hint was extremely helpful. $\endgroup$ – JackReacher Oct 14 '13 at 11:11
  • 1
    $\begingroup$ Please write up an Answer to your own Question, so others can benefit from your success! $\endgroup$ – hardmath Oct 14 '13 at 11:18
2
$\begingroup$

Although numbers of the form $10^n + 3$ (for $n=1,2,3,\ldots$) are never divisible by $2,3,5$, they are divisible by some prime $p$, possibly with the number $10^n + 3$ itself being that prime (e.g. $103$ is a prime).

Now Fermat's Little Theorem can be applied to deduce infinitely many composite numbers of the same form. That is, if $p$ divides $10^n + 3$, then $p$ is relatively prime to $10$ and:

$$ 10^{p-1} \equiv 1 \mod \; p $$

From this it follows that for every $k=1,2,3,\ldots$, we have $p$ divides $10^{n + k(p-1)} + 3$. Since $p \le 10^n + 3 \lt 10^{n + k(p-1)} + 3$, it follows that these latter numbers of the required form are composite.

Example: Since $7 | 10^4 + 3$, the numbers $10^{4+6k} + 3$ are composite.

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