2
$\begingroup$

Let $n$ be an integer greater than 10 such that everyone of its digits belongs to the set $S$=$\{1,3,7,9\}$. Show that $n$ has a prime divisor greater than or equal to 11.

Obviously n cannot have prime divisor 2 or 5 , now I have to show that n cannot equal to number of form $3^j 7^k$...

Till now I figured out that product of any two numbers of S taken mod 20 is still in the set itself..but I am not able to make any progress beyond this.

$\endgroup$
2
  • $\begingroup$ Forgive my ignorance, why do you have to show that $n$ cannot equal to a number of the form $3^j7^k$ ? $\endgroup$
    – IntegrateThis
    Jun 25, 2020 at 4:10
  • 2
    $\begingroup$ @IntegrateThis $n$ cannot have prime factors $2 $ or $5$ because of the unit digit and if it does not have any prime factor greater than or equal to $11$, what can be the prime factors of $n$? $\endgroup$
    – user-492177
    Jun 25, 2020 at 11:31

1 Answer 1

Reset to default
5
$\begingroup$

Suppose $n=3^j7^k$ for $j,k \geq 0$. Let $A=\{1,3,7,9\}$. By $mA$ we will denote the set $\{m,3m,7m,9m\}$. Then observe that (this is simple multiplication and then taking mod) \begin{align*} \{3,9,21,27\}=3A & \equiv A \pmod{20}\\ 7A & \equiv A \pmod{20}. \end{align*} Now we can use induction to prove that $3^j7^k \in A \pmod{20}$.This means $n$ has an even digit in the tens place (a contradiction).

$\endgroup$
4
  • $\begingroup$ How $3A \equiv A \pmod{20}\\$ ??? How two sets can be congruent . $\endgroup$
    – Ishan
    Jun 24, 2020 at 13:31
  • 2
    $\begingroup$ @Ishan That's just a made-up (shorthand) notation to say that when you apply $\mod 20$ to each entry of the set $3A$, then you end up getting the same set as $A$. $\endgroup$
    – Anurag A
    Jun 24, 2020 at 16:49
  • $\begingroup$ Why does this mean $n$ has an even digit in the tens place? $\endgroup$
    – IntegrateThis
    Jun 25, 2020 at 17:16
  • 2
    $\begingroup$ @IntegrateThis Think of it this way: if we have $n=100(x)+10y+z$, where $x$ is some integer and $y,z \in \{0,1,2, \ldots, 9\}$are the digits. Then $n \equiv 10y+z \pmod{20}$. If $y$ is even then $n \equiv z \pmod{20}$, otherwise $n \equiv 10+z \pmod{20}$. $\endgroup$
    – Anurag A
    Jun 25, 2020 at 18:04

You must log in to answer this question.

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