$4.$ Let there be a variable positive integer whose last two digits are $3's$. Prove that this number is divisible by a prime greater than $7$.
Problem
Source:
Tags: number theory, modular arithmetic
07.07.2019 20:00
According to the given information the actual number is $N=100n+33$, where $n$ is a non-negative integer. Assume $N$ has no prime divisors greater than 7. Clearly 2 and 5 are not prime divisors of $N$. Hence there must exist two non-negative integers $x$ and $y$ satisfying $(1) \;\; 100n + 33 = 3^x \cdot 7^y$. By (1) we have $(-1)^{x+y} \equiv 1 \pmod{4}$, yielding $x+y$ is even. If $x$ and $y$ are even, then $100n + 33$ is a perfect square, which is impossible since the last digit in a perfect square is 0,1,4,5,6 or 9. Consequently both $x$ and $y$ are odd. This means $3^x \cdot 7^y = 21z^2$, which according to equation (1) implies $z^2 \equiv3 \pmod{10}$, which is impossible. Hence equation (1) has no solution in non-negative integers $x$ and $y$. Consequently $N$ has a prime divisor greater than 7.
14.11.2021 20:24
Call the positive integer $n$ and AFTSOC $n=2^c\cdot3^a\cdot5^d\cdot7^b$. Since $2,5\nmid n$, $c=d=0$. So $n=3^a\cdot7^b$ and $n\equiv33\pmod{100}$. The residues of $7^n\pmod{100}$ are \[\{1,7,49,43\}.\]The residues of $3^m\pmod{100}$ are \[\{1,3,9,27,81,43,29,87,61,83,49,41,23,69,07,21,63,89,67\}.\] If $7^b\equiv1\pmod{100}$, we need $3^m\equiv33\pmod{100}$, which is not possible. If $7^b\equiv7\pmod{100}$, we need $3^m\equiv19\pmod{100}$, which is not possible. If $7^b\equiv49\pmod{100}$, we need $3^m\equiv 17\pmod{100}$, which is not possible. If $7^b\equiv43\pmod{100}$, we need $3^m\equiv 31\pmod{100}$, which is not possible. So we are done.