# Largest power of $3$ that divides $999\dots 999$ ($300$ $9$'s)

What is the largest power of $3$ that divides $999\dots 999$ ($300$ $9$'s)?

I have looked at the pattern of $9$, $99$, $999$, $9999$, $99999\dots 999999999$ and found the pattern that the largest power of $3$ that divides is: $2, 2, 3, 2, 2, 3, 2, 2, 4$

How would I work with prime factorization of this large power of $3$ that divides $999\dots 999$ ($300$ $9$'s)?

• Prime factorisation is likely to be extremely difficult for a number this size; not the best way to proceed. – Lord Shark the Unknown Jul 12 '18 at 14:36
• @LordSharktheUnknown apart from $3$s, the other factors are 7 × 11 × 13 × 31 × 37 × 41 × 61 × 101 × 151 × 211 × 241 × 251 × 271 × 601 × 2161 × 3541 × 4201 × 5051 × 9091 × 9901 × 21401 × 25601 × 27961 × 60101 × 261301 × 2906161 × 3903901 × 4188901 × 7019801 × 39526741 × 168290119201 × 182521213001 × 14103673319201 × 78875943472201 × 1680588011350901 × 25074091038628125301 × 15763985553739191709164170940063151 × 38654658795718156456729958859629701 × 10000099999999989999899999000000000100001 – Henry Jul 12 '18 at 14:51

Hints:

The number is $N=10^{300}-1$. The question is what is the largest $k$ with $3^k\mid N$, i.e., $10^{300}\equiv1\pmod{3^k}$. Now \begin{align} 10^{300}&=(1+9)^{300}=1+300\times 9+\binom{300}29^2+\binom{300}39^3+ \cdots\\ &=1+2700+81M \end{align} for some $M\in\Bbb N$. Then $N\equiv0\pmod{27}$ but $N\not\equiv0 \pmod{81}$.

• This is a good answer, but I would add another step before the last sentence to remind people that $N =0$ doesn’t mean that the equation equals zero. I got tripped up n that for a minute. Even just saying “then $N = 10^{300}-1=2700+81M$” would work. – Stella Biderman Jul 14 '18 at 7:51

$$10^{300}-1=(10^{75}-1)(10^{75}+1)(10^{150}+1)$$

now analyzing $10^{75}-1 = (9+1)^{75}-1\;\;$ which is divisible by $3^3 = 27$

Concluding

10^75 + 1 // FactorInteger

{{7, 1}, {11, 1}, {13, 1}, {211, 1}, {241, 1}, {251, 1}, {2161, 1}, {5051, 1}, {9091, 1}, {78875943472201, 1}, {10000099999999989999899999000000000100001, 1}}

10^150 + 1 // FactorInteger

{{61, 1}, {101, 1}, {601, 1}, {3541, 1}, {9901, 1}, {27961, 1}, {60101, 1}, {261301, 1}, {3903901, 1}, {4188901, 1}, {7019801, 1}, {39526741, 1}, {168290119201, 1}, {14103673319201, 1}, {1680588011350901, 1}, {25074091038628125301, 1}, {38654658795718156456729958859629701, 1}}

so finally we can conclude that the maximum is $3^3$

Your number $N$ can be expressed as $N = 10^{300}-1$

In the general formulation we have for numbers of such a form (by applying "Little" Fermat and Euler's totient and a bit more, see here) $$\{10^n -1 ,3\} = [n:1](2 + \{n,3\})$$ (where the braced expression $\{a,b\}$ means the highest power to which $b$ occurs in $a$, often called "valuation" or $v_b(a)$ and$[a:b]$ means $1$ if $b$ divides $a$ and $0$ if not)
this gives $$\{10^{300} -1 ,3\} = [300:1](2 + \{300,3\})=1\cdot(2+1)=3$$