3
$\begingroup$

Prove that every integer ending in 3 or 7 has a prime factor that also ends in 3 or 7.

I have that such an integer n has n=3 or 7(mod 10) but don't know where to go from there.

Then show that there are infinitely many prime numbers n with n=3 or 7 (mod 10)

$\endgroup$
  • 6
    $\begingroup$ Try to prove the contrapositive statement: if a positive integer $n$ does not have a prime factor that ends in $3$ or $7$ (i.e. prime factors are $2, 5$ or $p \equiv \pm 1 \pmod{10}$) then $n$ does not end in $3$ or $7$. $\endgroup$ – Ivan Loh Oct 16 '13 at 15:14
  • $\begingroup$ There are only a few digits that factors of $n$ can end in. What are they? $\endgroup$ – Empy2 Oct 16 '13 at 15:15
  • $\begingroup$ Well, of the four primes that are digits, only $\;3\;\;and\;\;7\;$ have multiples that end with $\;3\,,\,7\;$ . Add to that the prime $\;11\;$ and we're done... $\endgroup$ – DonAntonio Oct 16 '13 at 15:30
3
$\begingroup$

HINT:

First of all, any integer$(N)$ ending in $3$ or $7$ will not be divisible by $2,5$(why?)

So, the factors of $N$ must be $\equiv1,3,7,9\pmod {10}$

Observe that $1\cdot1 \equiv1, 9\cdot9\equiv1, 1\cdot9\equiv9 \pmod{10}$

So, the product of the primes(or their powers) $\equiv1,9\pmod{10}$ will be $\equiv1$ or $9\pmod{10}$

$\endgroup$
  • $\begingroup$ Surely you meant $1 \cdot 9 \equiv 9 \pmod{10}$. Fix it, please. $\endgroup$ – Smylic Oct 16 '13 at 15:45
  • $\begingroup$ @Smylic, thansk for your observation.Fixed $\endgroup$ – lab bhattacharjee Oct 16 '13 at 15:48
  • $\begingroup$ I have just added a second part, do you have an answer for it? $\endgroup$ – Rachel Oct 19 '13 at 11:07
  • $\begingroup$ @Rachel, math.stackexchange.com/questions/115121/primes-ending-in-7 and goo.gl/GocOSO. But, in general you can create a new problem to draw attention of more audience $\endgroup$ – lab bhattacharjee Oct 19 '13 at 12:55
1
$\begingroup$

Every prime number is congruent to $1,3,7$, or $9$ modulo $10$. Here is a a multiplication table modulo $10$

\begin{array}{c|cccc} \times & 1 & 3 & 7 & 9 \\ \hline 1 & 1 & 3 & 7 & 9 \\ 3 & 3 & 9 & 1 & 7 \\ 7 & 7 & 1 & 9 & 3 \\ 9 & 9 & 7 & 3 & 1 \\ \end{array}

Note that every integer ending in $3$ or $7$ had at least one divisor that ends in $3$ or $7$. Since a number can only have a finite number of divisors, it follows that at least one prime divisor must end in $3$ or $7$.

Since $\gcd(10,3) = \gcd(10,7) = 1$, Dirichet's theorem says that every arithmetic progression of the form $10n+3$ and $10n+7$ will contain infinitely many prime numbers.

$\endgroup$
1
$\begingroup$

Maybe "prime" is a Red Herring here. Show more generally: if a number ending in $3$ or $7$ is factored in any way (prime or not) then at least one of the factors ends in $3$ or $7$.

$\endgroup$
0
$\begingroup$

No product of two elements in $\{1,5,9\}\subset{\mathbb Z}_{10}$ is in $\{3,7\}$.

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