(A new question of the week)
Last time we looked at a classic problem for which there is a nice formula, namely counting all divisors of a given number. This time, we will examine a question from last August where we have to count the number of divisors of a specific type, making it more challenging. This also demonstrates what it can take to help someone without being sure what methods he will be able to understand (and without being an expert in this area myself). I find it helpful sometimes not to be an expert, because that lets me feel my way through a problem just as a student has to …
Not a trick question
Here is the question:
Q) Total number of divisors of N = (3^5).(5^7).(7^9) that are of form 4n+2, n≥0 , is equal to …
I gave a quick initial answer, knowing there must be more:
Hi, Arsh.
At first I thought this might be beyond my limited knowledge of number theory — I know how to find the total number of divisors; but only those of a certain form??
But then I looked again, and (unless I’m missing something) it seems so easy I’d almost call it a trick question.
If a number has the form 4n+2, what divisor do we know it has?
What kind of numbers can divide N?
What I saw here was that \(N = 3^5 5^7 7^9 = 766,088,007,890,625\) can’t have any divisors of the form \(4n+2\), because it is not even. So the answer is 0. But Arsh replied,
Sorry, by mistake I have written 4n+2 instead of 4n+1.
I see that for 4n+2 = 2(2n+1) we need one power of 2 and it is an odd no. so total should have been 0 as no power of 2 is present.
He saw my point! I replied,
Ah! Now it’s a much more interesting problem.
He continued,
I have checked powers of 3 and got 4n+1 is divisible by even powers of 3 – 3^0, 3², 3⁴.
Similarly I got that 4n+1 is divisible by all powers of 5.
And divisible by even powers of 7.
Total no. of ways = 3*8*5 = 120. But then I see at n = 5, we get 21 which is divisible by 3¹ and 7¹ which we have not counted.
This is where I have reached, please explain further.
This doesn’t quite make sense as written, though I could unravel it.
I offered a correction to his statements about \(4n+1\), where he surely can’t have meant to say that for any \(n\), \(4n+1\) is divisible by 5, 25, 125, …, for example.
I don’t think you mean what you said; it’s very easy to misstate facts about divisibility. I think you’re saying this:
I have checked powers of 3, and found that even powers of 3 (30, 3², 3⁴) are all of the form 4n+1.
Similarly I got that all powers of 5 are of the form 4n+1.
And even powers of 7 are of the form 4n+1.
Am I right?
To make sure that this is what he had determined, I had to make sure that the statements are correct:
Now, is this true? Starting with the last, 7^2 = 49 = 48 + 1 = 4*12 + 1, so it may be true; you didn’t say how you proved it, but one elementary way is to see that we want to show that 7^(2n) – 1 = 4k for any n, and in fact 7^(2n) – 1 = (7^n + 1)(7^n -1); both factors are even, so the conclusion is true. You may have a very different way to prove these facts; I’d like to know what it is, if only so I can see what your level of knowledge is. How much modular arithmetic do you know?
What I did here was to prove that, as he presumably meant to say, any even power of 7 (that is, any power of 49) has the form 4n+1 (for some integer n), by showing that \(49^n-1\) is a multiple of 4.
If I had thought that Arsh was familiar with modular arithmetic (and it turns out he is not), I could have shown this much more simply: since \(49 = 4\times12+1\), we know that \(49\equiv 1 (mod 4)\), and consequently \(49^n\equiv 1^n\equiv 1 (mod 4)\).
Or, I could do the same thing in terms of factoring: \(49^n = (48+1)^n = 48^n + … + 1 = 4k + 1\) because the binomial expansion of the power consists of terms that are multiples of 4, plus one final term that is 1.
The same can be done with each of the other claims. Since 9 and 5 are each 1 more than a multiple of 4, any power of either is also 1 more than a multiple of 4.
I continued, commenting on his conclusion:
You said,
Total no. of ways = 3*8*5 = 120. But then I see at n = 5, we get 21 which is divisible by 3¹ and 7¹ which we have not counted.
You’re right that counting pure powers of the right form will miss all the mixed products; I’m not sure whether this approach will be helpful.
The method I see that works starts with modular arithmetic. If you are sufficiently familiar with it, you might try thinking about factors of (3^5)(5^7)(7^9) mod 4. Start by thinking about 3, 5, and 7 mod 4.
He had been thinking that he had to consider only three powers of 3 (\(3^0, 3^2, 3^4\)), eight powers of 5 (\(5^0, 5^1, 5^2, 5^3, 5^4, 5^5, 5^6, 5^7\)), and five powers of 7 (\(7^0, 7^2, 7^4\)), for a total of \(3\times 8\times 5 = 210\) possible factors (using the same technique we looked at last time, multiplying the number of choices for each exponent). But then he realized that divisors of our N other than prime powers can have the form 4n + 1.
Arsh replied:
No I don’t know much of modular arithmetic. Although I know that any number mod 4 would mean finding the remainder.
I get (3^5)(5^7)(7^9) = (4k+1)(4k+3)² [ 3^5 mod 4 = 3 , 5^7 mod 4 = 1 , 7^9 mod 4 = 3] (by cyclicity or binomial)
Now, how can I reach the answer from here?
I’d be able to mention modular arithmetic, but not depend on it heavily. Arsh has mentioned two possible tools to use in its place; at this point I can’t be sure exactly what he means by using cyclicity (presumably observing some cyclical behavior) and binomial (the binomial formula), but they suggest he is doing some reasonable thinking. What he is saying, as I read it, is that \(3^5 = 4k+3\), \(5^7 = 4k+1\), and \(7^9 = 4k+1\), each for some integer value of k, which is equivalent to saying \(3^5 \equiv 3 (mod 4)\), \(5^7 \equiv 1 (mod 4)\), and \(7^9 \equiv 1 (mod 4)\), respectively. Probably “cyclicity” means that he observed, for example, that \(3^1 = 3 = 4\times0 + 3\), \(3^2 = 9 = 4\times2 + 1\), and subsequent powers will repeat this pattern: \(3^3 = 27 = 4\times8 + 3\), \(3^4 = 81 = 4\times20 + 1\), \(3^5 = 243 = 4\times60 + 3\), … . Once a power leaves a remainder of 1, remainders repeat. Something similar can be done using a binomial expansion as I did before for 49, but I’m not sure exactly what his approach is. What I know is that he is doing some good thinking, but needs a little more guidance. So I answered,
Hi, Arsh.
What you say,
I get (3^5)(5^7)(7^9) = (4k+1)(4k+3)² [ 3^5 mod 4 = 3 , 5^7 mod 4 = 1 , 7^9 mod 4 = 3] (by cyclicity or binomial)
is not valid, but it shows you have an important part of the idea. Primarily, you can’t use the same k for different numbers. Secondarily, this specific statement, even after correction to (3^5)(5^7)(7^9) = (4i+3)(4j+1)(4k+3), is probably not quite on the path to an answer. But something very close to it is.
The use of the same constant k in three places, where they will actually be three different integers, is a common mistake in doing this kind of work; in one sense it is a minor error that could be overlooked if he knows what he means, but it can lead to major trouble if what was written is used as written.
In terms of modular arithmetic, what Arsh has done is definitely on the right path; he has shown that \(3^5 5^7 7^9 \equiv 1\cdot3^2 = 9 \equiv 1 (mod 4)\), which could work nicely. But using the tools he has, he will probably miss the mark.
I continued,
I’d like to see exactly what you mean by “cyclicity or binomial”; both of those are appropriate, and seeing how you perceive them might help me express things appropriately for your background. You may know enough of modular arithmetic to use it here; but binomials may be easier for you.
But let’s try this approach: First, note that 3 ≡ -1 (mod 4), 5 ≡ 1 (mod 4), and 7 ≡ -1 (mod 4), Note that I have used -1 in place of your 3, which will make what follows easier. If you don’t understand my notation or my use of -1 (which is not what we typically think of as a remainder), then we’ll have to use the binomial approach.
I expressed this in terms of modular arithmetic, since Arsh had shown some familiarity with the notation. The idea is that whereas we normally think of a remainder as positive, we don’t have to use that as our “final” form all the time; we can choose whatever representation will be easiest to work with. Here, I chose to write 3 as \(1\cdot 4 – 1\) rather than as \(0\cdot 4 + 3\), because it is easier to work with -1 than with 3.
In closing, I expressed the same idea in those terms, and gave references that explain the notations and concepts of modular arithmetic. [Note to self: let’s have a post about that soon …]
Now, rather than focusing on 3^5, 5^7, and 7^9, think about any powers, i.e. 3^m, 5^n, and 7^p. What can you say about each of these, mod 4?
In terms of binomials, I would say that 3^m = 4i – 1, 5^n = 4j + 1, and 7^p = 4k – 1. What, then, can you say about their product?
For some information on modular arithmetic, see
Three days later, Arsh got back to me:
Sorry for the late reply. I know what you mean by negative remainders, but I still can’t reach to the answer. By observing the product as you told me, I get that putting various values of i, j and k give me all the combinations of numbers but how to proceed further.. ..
We don’t have the further information I’d hoped for (about methods being used or specific attempts made), so I just answered with a more specific hint:
We’re trying to count numbers of the form 3^m 5^n 7^p, where 0 ≤ m ≤ 5, 0 ≤ n ≤ 7, 0 ≤ p ≤ 9, that are congruent to 1 (mod 4).
I’ve pointed out that 3 ≡ -1 (mod 4), 5 ≡ 1 (mod 4), and 7 ≡ -1 (mod 4). So you can think of it as looking for numbers of the form (-1)^m (1)^n (-1)^p, where 0 ≤ m ≤ 5, 0 ≤ n ≤ 7, 0 ≤ p ≤ 9, that are equal to 1. What is required of the exponents for this to be true?
The first paragraph explicitly states what has been in the background all along, but never explicitly stated, and which we used last week for the general case of counting divisors: We will be counting all combinations of the three exponents, within their ranges, that will yield a result congruent to 1 (that is, leaving remainder 1). It is often helpful to explicitly state the goal so we can relate it to what we are doing.
The second paragraph restates that goal in terms of modular arithmetic (hoping that Arsh understands enough to apply this idea to whatever method he ends up using).
Within half an hour, Arsh got back to me:
I think I have found an answer.
Case 1: Even values of m, p and all values of n. 3*8*5=120
Case 2: When m and p both are odd and all values of n. 3*8*5=120
So total values 240.
I think I have understood how to do it by binomial theorem also.
Numbers are of form – (4i-1)^m (4j+1)^n (4k-1)^p
(4i-1)^m = 4h-1 where h is any integer. (All terms except -nCn are divisible by 4)
Similarly we get for rest 2 factors – and following the steps as you told
Good! What Arsh has seen is that the exponents on 3 and 7 can both be even, or both be odd; this is because in order to get 1 from powers of -1, we need either two positive numbers or two negative numbers. The exponent on 5 can be anything. In each case, this gives us 3 choices for m (1, 3, 5, or 0, 2, 4) and 5 choices for p (1, 3, 5, 7, 9, or 0, 2, 4, 6, 8), and 8 choices for n (0, 1, 2, 3, 4, 5, 6, 7). That gives a total of 120 possible divisors in each case, and 240 in all.
Then he expressed the same in terms of binomials, where only the last term matters. This could have been done with the 3’s instead of the -1’s, but would have needed an extra step or two, and would have been harder to see.
I congratulated him:
You got it!
And, yes, binomials are just a slightly bulkier way to say the same thing. Modular arithmetic just makes what has to be done more visible.
Also, this trick of seeing the remainder as -1 rather than n-1 (mod n), because -1 has nicer properties, is useful in a number of other familiar problems. That’s why I saw it easily, having seen it before.
It was another nice problem, and led to a good discussion. I always like it when I can trust a student to be able to take hints and run farther with them, rather than need to be led along by the hand; and I think using modular concepts to state the hint helped to stretch his understanding.