2
$\begingroup$

Consider the number $A_{1395}=\underbrace{333\cdots3}_{1395}$. what is the maximum value of $m$ where $3^m$ be a factor of $A_{1395}$.

$a) 2\quad\quad b)3\quad\quad c)4\quad\quad d)5\quad\quad e)6$

Here is my attempt :

We have $A_{1395}=3\times \underbrace{111\dots1}_{1395}$ sum of the digits of $\underbrace{111\cdots1}_{1395}$ is $1395$ which is a multiply of $9$. therefor this number is dividable to $9$. so we conclude $A_{1395}$ has the factor $3^3$ . to see whether it has more factor of $3$ or not I divided it to $27$. after doing some steps of long division I got:

$$\underbrace{11\cdots1}_{1395}÷27=4115226\cdots$$ Unfortunately I couldn't see any pattern as the result. so I don't know how to check this number has more factor of $3$ or not.

$\endgroup$
5
  • 1
    $\begingroup$ Hint: the LTE-lemma $\endgroup$
    – leoli1
    Feb 7, 2021 at 11:36
  • $\begingroup$ I'm not sure how to get the result quickly in an explicit form, but you can easily find it with a short search in this case. To get started, just imagine your number as $(10 ^ {1395} - 1) / 3$. If it is divisible by $3 ^ m$, then $10 ^ {1395} - 1$ is divisible by $3 ^ {m + 1}$. So $10 ^ {1395}$ is comparable to $1$ modulo $3 ^ {m + 1}$. Now you just need to find the largest suitable m. $\endgroup$
    – EzikBro
    Feb 7, 2021 at 11:37
  • $\begingroup$ Amazing: they already did Math Olympiads in 1395 $\endgroup$
    – Raffaele
    Feb 7, 2021 at 12:07
  • 1
    $\begingroup$ @Raffaele it is an Olympiad problem from Iran. it was for $1395$ from Solar calendar ;) (about $4$ years ago) $\endgroup$
    – Etemon
    Feb 7, 2021 at 12:09
  • $\begingroup$ LMAO! I got it! It was the Iranian calendar @Soheil $\endgroup$
    – Raffaele
    Feb 7, 2021 at 12:18

4 Answers 4

4
$\begingroup$

Write using the binomial theorem, \begin{align} 999\cdots 9 &= 10^{1395} -1 \\ &= (1+9)^{1395} -1 \\ &= \left(\array{1395\\1}\right)\cdot 9 + \left(\array{1395\\2}\right)\cdot9^2 + \cdots 9^{1395} \end{align} But $1395 = 3^2 \cdot 5 \cdot 31$. So, the first term is divisible by $3^4$ and each term thereafter is divisible by $3^5$ meaning the sum is divisible $3^4$ and not by $3^5$. Accordingly, $333\cdots 3$ is divisible by $3^3$ but not $3^4$. The answer is therefore $3$.

$\endgroup$
3
  • $\begingroup$ @Raffaele thanks for correcting! $\endgroup$
    – WA Don
    Feb 7, 2021 at 12:20
  • $\begingroup$ Nice solution ;) $\endgroup$
    – Etemon
    Feb 7, 2021 at 12:36
  • $\begingroup$ @Soheil Thank you. $\endgroup$
    – WA Don
    Feb 7, 2021 at 12:41
2
$\begingroup$

We write the number as ${10^{1395}-1\over 3}$

By Euler Thorem, $10^{162}\equiv1\pmod{243}$ so $10^{1395}\equiv10^{99}\pmod{243}$

Since $10^{99} \equiv 28^{33}\equiv82^{11}\equiv(-80)^5\times82\equiv82^2\times(-80)\times82\equiv(-80)^2\times82\equiv-80\equiv163\pmod{243}$

We know $10^{99}-1\equiv162\pmod{243}$ which implies $10^{1395}-1\equiv 162\pmod{243}$

Therefore $10^{1395}-1$ is not a multiple of $243$ but is a multiple of $81$.

So ${10^{1395}-1\over 3}$ is a not multiple of $81$ but is a multiple of $27$

$\endgroup$
2
$\begingroup$

For $x\in\Bbb N$, letr $v_3(x)$ be the exponent of the maximal power of $3$ dividing $x$.

If $n=3^ka+1$ with $k\ge1$ and $3\nmid a$, then $$ n^3=3^{3k}a^3+3^{2k+1}a^2+3^{k+1}a+1 =3^{k+1}(a+3^k(\ldots))+1$$ i.e.,

If $v_3(n-1)>0$ then $v_3(n^3-1)=1+v_3(n-1)$.

Note that $A_{1395}=\frac{10^{1395}-1}3$, so what we are looking for is $m=v_3(10^{1395}-1)-1$. By the above remark, $$m=v_3(10^{1395}-1)-1=v_3(10^{465}-1) = v_3(10^{155}-1)+1. $$ Also, as $v_3(10^3-1)=1+v_3(10-1)=3$, so that $$ 10^{155}=(10^3)^{51}\cdot 100\equiv 100\equiv 19\pmod{27}$$ (but $\equiv 1\pmod 9$). We conclude $$v_3(10^{155}-1)=2 $$ and ultimately $$ v_3(A_{1395})=3.$$

$\endgroup$
1
$\begingroup$

Consider an extension 9f the familiar sum of digits test for divisibility by $9$.

The number $999$ factors as $27×37$ or with prime factors, $3^3×37$. Thus if you add three-digit blocks together to cast out multiples if $999$, you are also casting out multiples of $27$ and $37$ and thus the sum of tyree-digit blocks tests for divisibility by these factors.

This can be extended to higher powers of $3$. The sum of nine-digit blocks tests for divisibility by $81$, and more generally adding blocks of $3^k$ digits tests for divisibility by $3^{k+2}$

In your case, then, first sum the three-digit blocks to get $333×465$ where each of $465$ blocks is $333$. Since $333$ is a multiple of $9$ and $465$ is a multiple of $3$, your three-digit block sum passes for divisibility by $27$.

Next try the nine-digit block sum getting $333333333×155$. The three-digit blocks of $333333333$ add up to a multiple of $27$, but dividing out a factor of $3$ gives $111111111$ which fails that test. So $333333333$ is a multiple of $27$ but not $81$, and $155$ is not a multiple of $3$, so the nine-digit block sum which equals their product fails divisibility by $81$.

Thus the maximum power of $3$ that divides $A_{1395}$ is $3^3=27$.

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