Problem:
Let n be the least positive integer for which 149n−2n is divisible by 33⋅55⋅77. Find the number of positive integer divisors of n.
Solution:
Let's go prime by prime, starting with the factor of 33
First off, notice that 147=3⋅49 and so it has a power of 3 in it.
Thus, notice how we can represent 149n−2n as
(147+2)n−2n
and the former expression can be factored using the Binomial Theorem as
(147+2)n−2n
(0n)2n+(1n)⋅2n−1⋅1471+(2n)2n−21472+...+(nn)⋅20⋅147n−2n
and after the first power of 2n is eliminated, notice that this is immediately divisible by 33 once n is divisible by 32 in order for the 147n term to be divisible by 33.
Now, let's move on to the power of 55
Let's rewrite out expression mod 5 to start.
149n−2n≡4n−2n≡2n(2n−1)≡0mod5
For this to evaluate to 0 mod 5, we need
2n≡1mod5
or for n≡4mod5
Thus, since n is divisible by 4, we can write n=4k and rewrite our given expression as
149n−2n=(1494)k−(24)k
From here, we see that conveniently 1494≡26mod55 and that 24≡16mod55
so we can rewrite our expression as
(1494)k−(24)k≡26k−16k≡(16+10)k−16kmod55
Remember that 10 only has one power of it, and so when we expand using binomial theorem again we get
(0k)⋅16k⋅100+(1k)⋅16k−1⋅101+(2k)⋅16k−2⋅102+⋯−16k
which has only 1 power of 5 in it, limited by the (1k)16k−1101 term.
Thus, we'd need 54∣k or for 4⋅54∣n
Lastly, we have to deal with the 77 term.
We directly apply binomial theorem again, rewriting it using the fact 149=147+2 as follows
(0n)⋅2n⋅1470+(1n)⋅2n−1⋅1471+(2n)⋅2n−2⋅1472+⋯−2n
Given that 147=72⋅3, the terms that are important to us are the 1471 term, the 1472 term, and the 1473 term, and the most "limiting" term is the 1471 term, where we need 77∣1471 or for 75∣n.
Thus, we've found that
32∣n
4⋅54∣n
75∣n
so the minimum n is the lcm of these which is
22⋅32⋅54⋅75
who's factors is
(2+1)(2+1)(4+1)(5+1)=270
OLD SOLUTION
Analyze each prime power separately. Start with the case of 33. By the Binomial Theorem,
149n−2n=(147+2)n−2n=(1n)⋅147⋅2n−1+(2n)⋅1472⋅2n−2+(3n)⋅1473⋅2n−3+⋯
Because 147 is divisible by 3, all terms after the first two are divisible by 33, and the exponent of 3 in the first term is less than that in the second term. Hence it is necessary and sufficient that 33∣147n, that is, 32∣n. For the 77 case, consider the same expansion as in the previous case. Because 147 is divisible by 49=72, all terms after the first three are divisible by 77, and the exponent of 7 in the first term is less than that in the second and third term. Hence it is necessary and sufficient that 77∣147n, that is, 75∣n. For the 55 case, working modulo 5 gives 149n−2n≡4n−2n=2n(2n−1)(mod5), so it must be that 4∣n. Let n=4m, and let c=1494−24=(1492−22)(1492+22)=147⋅151⋅22205. Note that 5c is an integer not divisible by 5. Expand by the Binomial Theorem again to get
(1494)m−(24)m=(c+16)m−(16)m=(1m)⋅c⋅16m−1+(2m)⋅c2⋅16m−2+(3m)⋅c3⋅16m−3+(4m)⋅c4⋅16m−4+⋯
All terms after the first four are divisible by 55, and the exponent of 5 in the first term is less than that in the second, third, or fourth term. Hence it is necessary and sufficient that 55∣cm. Thus 54∣m, and it follows that 4⋅54∣n. Therefore the least n is 32⋅(22⋅54)⋅75. The requested number of divisors is (1+2)(1+2)(1+4)(1+5)=270. The results of the above cases can be generalized using the following lemma.
Lifting the Exponent Lemma: Let p be an odd prime, and let a and b be integers relatively prime to p such that p∣(a−b). Let n be a positive integer. Then the number of factors of p that divide an−bn is equal to the number of factors of p that divide a−b plus the number of factors of p that divide n.
The problems on this page are the property of the MAA's American Mathematics Competitions