4
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ Prime factorisation is likely to be extremely difficult for a number this size; not the best way to proceed. $\endgroup$ – Lord Shark the Unknown Jul 12 '18 at 14:36
  • $\begingroup$ @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 $\endgroup$ – Henry Jul 12 '18 at 14:51
4
$\begingroup$

Hints:

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Stella Biderman Jul 14 '18 at 7:51
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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