# find the maximum value of $m$ where $3^m$ be a factor of $A_{1395}$.

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.

• Hint: the LTE-lemma Feb 7, 2021 at 11:36
• 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. Feb 7, 2021 at 11:37
• Amazing: they already did Math Olympiads in 1395 Feb 7, 2021 at 12:07
• @Raffaele it is an Olympiad problem from Iran. it was for $1395$ from Solar calendar ;) (about $4$ years ago) Feb 7, 2021 at 12:09
• LMAO! I got it! It was the Iranian calendar @Soheil Feb 7, 2021 at 12:18

## 4 Answers

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

• @Raffaele thanks for correcting! Feb 7, 2021 at 12:20
• Nice solution ;) Feb 7, 2021 at 12:36
• @Soheil Thank you. Feb 7, 2021 at 12:41

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

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

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