2018 AIME I Problems/Problem 11

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, $39 \mid n$ .

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

-expiLnCalc

Solution

Note that Euler's Totient Theorem would not necessarily lead to the smallest $n$ and that in this case that $n$ is greater than $1000$ .

We wish to find the least $n$ such that $3^n \equiv 1(\mod 143^2)$ . This factors as $143^2=11^{2}*13^{2}$ . Because $gcd(121, 169) = 1$ , we can simply find the least $n$ such that $3^n \equiv 1(\mod 121)$ and $3^n \equiv 1(\mod 169)$ .

Quick inspection yields $3^5 \equiv 1(\mod 121)$ and $3^3 \equiv 1(\mod 13)$ . Now we must find the smallest $k$ such that $3^3k \equiv 1(\mod 13)$ . Euler's gives $3^156 \equiv 1(\mod 169)$ . So $3k$ is a factor of $156$ . This gives $k=2, 4, 13, 26, 52$ . Some more inspection yields $k=13$ is the smallest valid $k$ . So $3^5 \equiv 1(\mod 121)$ and $3^39 \equiv 1(\mod 169)$ . The least $n$ satisfying both is $lcm[5,39]=\boxed{195}$ . (RegularHexagon)

Page

Toolbox

Search

2018 AIME I Problems/Problem 11

Solutions

Modular Arithmetic Solution- Strange (MASS)

Solution