Subtracting powers
Find the smallest possible positive value of 3 3 m − 7 n , where m and n be positive integers.
The answer is 26.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Where does the 16 come from?
Log in to reply
The 16 and 3 are clever choices designed to narrow down the set of possible differences. There's no hard and fast rule about which modulus to choose for these kind of problems, but the moduli are usually chosen to give a residue of 0 or 1 for some or all of the terms.
See Diophantine Equations - Modular Arithmetic Considerations for some similar problems.
Excellent problem and solution! I edited your solution a bit -- just to fix some of the formatting.
In fact, where do both the 16 and the 3 come from? And given the possibilities, how does that mean that 26 is the smallest possible outcome?
Log in to reply
See my comment to Jonathan for why the moduli were chosen.
26 is the smallest possible value because it is the smallest possible solution to the system:
{ 3 3 m − 7 n ≡ 0 or 1 0 ( m o d 1 6 ) 3 3 m − 7 n ≡ 2 ( m o d 3 )
I wrote the answer as 26, and it said incorrect. I then wrote 16, but that was 7^2-33^1 , but 33^1-7^2= -16, so that was wrong. I didn't have a proof, but why did it say that 26 was incorrect?
What if m is 1 and n is 2; or m is 2 and n is 5 or even 9? Think I have missed something obvious here!
Log in to reply
The problem asks for the smallest positive value. The differences you cited are negative.
We know that, anything 1 = anything .
Since 1 is a positive integer, so m = 1 and n = 1
⇒ 3 3 1 − 7 1 = 3 3 − 7 = 2 6
As the condition of m and n barely says "be positive integers", it means that m and n could be equal. Having m=2 and n=1, the value is too large to be the answer. Therefore, m=n=1 would be the values, while evaluating the expression gives us 26 as the minima (remember that the result should be a POSITIVE INTEGER).
Why cannot there be a solution when n > m ?
Yes it can be possible to take n>m, but the gap between those will get more wider. There will be only one case when m=n=1 to find min difference.
Log in to reply
Can you show that the gap gets wider? Yes, if m = n , then that is the minimum, but that doesn't mean that it is always the minimum.
If m = 1 and n = 1 , the difference is 26.
To show that no smaller difference is possible, we check the remainder when divided by 16 and by 3:
When divided by 16,
3 3 m ≡ 1 ( m o d 1 6 ) , 7 2 k ≡ 1 ( m o d 1 6 ) , 7 2 k + 1 ≡ 7 ( m o d 1 6 )
So 3 3 m − 7 n ≡ 0 or 1 0 ( m o d 1 6 )
Possibilities are 0, 10, 16, and 26.
When divided by 3,
3 3 ≡ 0 ( m o d 3 ) and 7 ≡ 1 ( m o d 3 )
So 3 3 m − 7 n ≡ 2 ( m o d 3 )
Thus 26 is the smallest possibility, which has been achieved by 3 3 1 − 7 1 = 2 6 .