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, 2013 at 10:36
  • $\begingroup$ I did think of that, but I see that for example $7 \nmid 10^7+3$, which is composite. $\endgroup$ Oct 14, 2013 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, 2013 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$ Oct 14, 2013 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, 2013 at 11:18

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .