Find a positive integer with prime factors of at most 2, 3, 5, 7 and ends in the digits 11

Question

Does there exist a positive integer whose prime factors include at most 2, 3, 5, and 7, and ends in the digits 11? If so find the smallest positive integer. If not, show why none exists.

My professor gave us this question to think over. She also gave us a hint to work in mod20.

I'm not sure why we are working in mod20. I thought it might be because anything that ends in the digits 11 will be congruent to 11 (mod20). I had a thought that the prime factorization cannot include 2 because the number is not even, nor can it include 5 since the number is not a multiple of 5. Otherwise, I am at a loss...

Any help or guidance would be greatly appreciated!

Answer 1

Working in modulo 10 will be enough to give you the answer for 2 of the factors. Just try it on your calculator. Extend the technique to modulo 20 to finish the job for the other factors.

Answer 2

If the number ends in $11$, it will, as you said, be congruent to $11\mod 20$ and the prime factors $2$ and $5$ can be excluded, so $$n = 3^a \cdot 7^b$$ Now $3\cdot 7 = 21 \equiv 1 \pmod{20}$ so $$n \equiv \cases{3^{a-b} & $a>b$ \\ 7^{b-a} & $b>a$\\1 & $a=b$} \pmod{20}$$ Now look at $3^k$ and $7^k$ in $\mod 20$ to conclude.

Answer 3

Clearly, $2$ and $5$ cannot divide the number. Hence, let the number be of the form $3^a7^b$. We have $$3^a \equiv 1,3,9,7 \pmod{20} \text{ and }7^b \equiv 1,7,9,3\pmod{20}$$ Hence, $$3^a7^b \equiv 1,3,7,9\pmod{20}$$ However, the number ending in $11$ is $\equiv 11\pmod{20}$.

Answer 4

Proof by contradiction: Suppose such a number $n$ exists. $2, 5$ cannot divide such a number; therefore, it must be a multiple of either $3,7$. Express $n$ as: $$n=3^a\cdot 7^b$$ If $a=b$, we find that $n=21^a$, and $21^a\space$mod$(20)=1, \space \space \forall a\in \mathbb{N}$. Since we want $n \space$mod$(20)=11$, we can rule out the case when $a=b$.

Now suppose $a>b$. Let us reexpress $n$ as: $$n = 3^a\cdot 7^b = 3^{a-b}\cdot 3^b\cdot7^b=3^{a-b}\cdot21^b$$

Note that $21^b$mod $20=1,$ and $3^{a-b}$mod $20=\{1,3,5,7\}$. Thus,

$$(3^{a-b}\cdot21^b)\space mod(20)=\{1,3,5,7\}.$$

The same reasoning would apply if $b>a$, and therefore, such a number does not exist.