Problem:
Find the least positive integer n such that when 3n is written in base 143, its two right-most digits in base 143 are 01.
Solution:
The requested positive integer is the least value of n>0 such that 3n≡ 1(mod1432). Note that 143=11⋅13. The least power of 3 that is congruent to 1 modulo 112 is 35=243=2⋅112+1. It follows that 3n≡ 1(mod112) if and only if n=5j for some positive integer j.
The least power of 3 that is congruent to 1 modulo 13 is 33=27=2⋅13+1. It follows that 3n≡1(mod13) if and only if n=3k for some positive integer k. Additionally, for positive integer k, the Binomial Theorem shows that 33k=(26+1)k≡26⋅k+1(mod132). In particular, 3n=33k≡ 1(mod132) if and only if k=13m for some positive integer m, that is, if and only if n=39m.
Because 112 and 132 are relatively prime, 3n≡1(mod1432) if and only if 3n≡1(mod112) and 3n≡1(mod132). This occurs if and only if n is a multiple of both of the relatively prime integers 5 and 39, so the least possible value of n is 5⋅39=195​.
The problems on this page are the property of the MAA's American Mathematics Competitions