2018 AIME I Problems/Problem 11

Revision as of 19:00, 7 March 2018 by Mathislife16 (talk | contribs) (Modular Arithmetic Solution- Strange (MASS))

Find the least positive integer $n$ such that when $3^n$ is written in base $143$, its two right-most digits in base $143$ are $01$.

Solutions

Modular Arithmetic Solution- Strange (MASS)

Note that $3^n \equiv 1 (\mod 143^2)$. And $143=11*13$. Because $gcd(11^2, 13^2) = 1$, $3^n \equiv 1 (\mod 121 = 11^2)$ and $3^n \equiv 1 (mod 169=13^2)$.

If $3^n \equiv 1 (\mod 121)$, one can see the sequence $1, 3, 9, 27, 81, 1, 3, 9...$ so $5 \mid n$.

Now if $3^n \equiv 1 (\mod 169)$, it is harder. But we do observe that $3^3 \equiv 1 (\mod 13)$, therefore $3^3 = 13a + 1$ for some integer $a$. So our goal is to find the first number $p_1$ such that $(13a+1)^ {p_1} \equiv 1 (\mod 169)$. In other words, the $a$ coefficient must be $0 (\mod 169)$. It is not difficult to see that this first $p_1=13$, so ultimately $3^39 \equiv 1 (\mod 169)$. Therefore, $n \mid 39$.

The first $n$ satisfying both criteria is $5*39=\boxed{195}$.

-expiLnCalc