Find the natural number $pq57r$ written in the decimal system , is divisible by $729$ then find $p,q,r$

Question

Problem :

Find the natural number $pq57r$ , is written in the decimal system , is divisible by $729$ then find $p,q,r$

My attempt as following :

$\bar {pq57r}\equiv 0\pmod{729}$

$10000p+1000q+500+70+r\equiv 0\pmod{729}$ Now I don't know how to complete my work ?

Answer 1

Note that if $729\times m$ is a 5-digit number, then $m\lt100{,}000/729=137.174\ldots$. Now if $729m=pq57r$ for some digits $p$, $q$ and $r$, then in particular we have

$$729m\equiv570+r\pmod{1000}$$

with $0\le r\le9$, so we can see which digit(s) $r$ allow for a solution of this congruence with a value of $m$ that is less than $137$. To do this, we need to compute the inverse of $729$ mod $1000$. Since $729=3^6$ and the inverse of $3$ mod $1000$ is $-333$, the inverse of $729$ is

$$(-333)^6=333^6=333^3\cdot3^3\cdot111^3\equiv-111^3\equiv-631\equiv369\pmod{1000}$$

(where the tricky part was to cube the $111$, keeping only the last three digits). Thus

$$m\equiv369(570+r)\equiv330+369r\pmod{1000}$$

(using a calculator to obtain $369\cdot570=210{,}330$ to get the $330$) We now have ten things to compute:

$$\begin{align} r=0&\implies330+369r=330\\ r=1&\implies330+369r=699\\ r=2&\implies330+369r=1068\\ r=3&\implies330+369r=1437\\ r=4&\implies330+369r=1806\\ r=5&\implies330+369r=2175\\ r=6&\implies330+369r=2544\\ r=7&\implies330+369r=2913\\ r=8&\implies330+369r=3282\\ r=9&\implies330+369r=3651 \end{align}$$

Among these, only $r=2$ gives a value for $m$ mod $1000$, namely $m=68$, that is less than $137$. Computing, we have

$$729\times68=49572$$

so $p=4$, $q=9$, and $r=2$.

Remark: There may be some easier way to show that $r=2$ is the only solution, but it's not all that hard to compute all ten values

Answer 2

First, do a balanced reduction for everything mod $729$ to make the numbers smaller: $$ -206p + 271 q - 159 + r\equiv 0\mod 729. $$

Now, compute the remainders for $-206p$ and $271q - 159$ for $p =1...9$ and $q = 0...9$. The results sorted from lowest to highest are $$ p: -301, -206, -190, -95, 16, 111, 222, 317, 333 \\ q: -346, -262, -178, -159, -75, 9, 93, 112, 196, 280. $$ Since adding $r$ has to leave us with $0$ mod $729$, we need a positive and negative pair that sum to between $-9$ and $0$. You can verify by inspection the unique such pair is $(-95, 93)$. So $r= 2$, and the $p$ and $q$ that gave those remainders were $4$ and $9$.

Thus, the number is $49572 = 729\cdot 68$.

Answer 3

$729=9^3 = (10-1)^3 = 1000 - 300 +30 -1$

so if $(10a +b)*729 = pq,57r$ where $b$ is a digit (but $a$ is a number $1\le a \le 13$) then

$(10a + b)(1000-300 + 30-1) =$

$10,000a + 1,000(b-3a) + 100(3a-3b) + 10(3b-a) - b=$

$10,000p + 1,000q + 500 + 70 +r$.

So $-b \equiv r\pmod 10$

We can rule out $b=0$ quickly. That would mean

$1,000a - 300a + 30a - a = pq57$

which would mean $a \equiv 3 \pmod {10}$. If $a = 10c + 3$ then

$7290*c + 3000- 900 + 90 -3 = 7290c + 2187=pq57$

So $729c + 218 = pq5$ which can only happen if $c\equiv 3\pmod {10}$ which simply makes for too high a number.

So $r = 10-b$.

And we have:

$10,000a + 1,000(b-3a) + 100(3a-3b) + 10(3b-a) - b=$

$10,000p + 1,000q + 500 + 80 -b$.

So:

$1,000a + 100(b-3a) + 10(3a-3b) + (3b-a)=$

$1,000p + 100q + 50 + 8$.

And $3b-a \equiv 8\pmod {10}$.

$-9 \le 3b-a \le 26$ so $3b-a= -2,8,18$

Let $3b-a = 10d + 8$ where $d=-1,0,1$.

Then

$1,000a + 100(b-3a) + 10(3a-3b) + 10d +8=$

$1,000p + 100q + 50 + 8$.

So:

$100a + 10(b-3a) +(3a-3b) +d=$

$100p + 10q + 5$

$3a-3b + d\equiv 5\pmod {10}$ and $3b-a \equiv 8 \pmod{10}$ so

$3a-3b+d + 3b-a = 2a + d\equiv 5+8\equiv 3\pmod{10}$.

but that's only possible if $d$ is odd.

At this point we have 5 cases:

1) $d=-1$ and $2a - 1\equiv 3\pmod{10}$ so $2a \equiv 4 \pmod {10}$ and $a\equiv 2\pmod {10}$. And as $1\le a \le 13$ we have $a=2$.

2) $d=-1$ so $2a \equiv 4\pmod {10}$ and $a \equiv 7\pmod {10}$. So $a=7$

3) $d=1$ and $2a\equiv 2\pmod{10}$ and $a\equiv 1\pmod {10}$. $a=1$.

4) $d=1$ and $a\equiv 1\pmod {10}$ and $a=11$.

5) $d= 1$ and $2a\equiv 2\pmod{10}$ and $a\equiv 6\pmod {10}$. $a = 6$

Case 1:

$100a + 10(b-3a) +(3a-3b) +d=$

$100p + 10q + 5$

so

$200 + 10(b-6) +(6-3b) =$

$100p + 10q + 6$

So

$140 + 7b = 100p + 10q$ which is impossible ($7b\equiv 0\pmod{10}$ means $b = 0$ and we ruled that out.)

Case 2:

$100a + 10(b-3a) +(3a-3b) +d=$

$100p + 10q + 5$

so

$700 + 10(b-21) +(21-3b) =$

$100p + 10q + 6$

So $490 + 7b + 15 = 100p +10q$ which means $b=5$. so $490+35+15=540$

So $10a+b = 75$ but $75*729\ne 54575$.

Case 3:

$100a + 10(b-3a) +(3a-3b) +d=$

$100p + 10q + 5$

So

$100 + 10(b-3) +(3-3b) =$

$100p + 10q + 4$

And $70 + 7b + 3 = 100p +10q + 4$ or $70 + 7b= 100p+10q + 1$ which requires $b=3$ and $91$ and $p=0$; $q=9$. But $13*729 \ne 9577$

Case 4:

$100a + 10(b-3a) +(3a-3b) +d=$

$100p + 10q + 5$

So

$100 + 10(b-33) +(33-3b) =$

$100p + 10q + 4$

$-230 +7b + 33 = 100p + 10q + 4$ and ... oh, come on, that's a negative number.

Case 5:

$100a + 10(b-3a) +(3a-3b) +d=$

$100p + 10q + 5$

So

$600 + 10(b-18) + (18-3b)= 100p + 10q + 4$

So

$420 +7b + 14 = 100p + 10q$ so $b=8$ and

$420 + 56+14 = 590$ so $p,q = 5,9$ and $r =10-8=2$ and $68*729 = 59572$

=====