Suppose that a and b are positive integers, such that for every positive integer n ,
3 n 3 + 5 n 5 + b a n
is an integer. What is the smallest possible value of a + b ?
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.
Graaah I hate it when I accidentally press "Enter discussion" instead of "write solution". (In this vein, apologies if i seem to be spamming on your solution, Daniel)
Through Fermat's Little Theorem, we have 3 ∣ n 3 − n and 5 ∣ n 5 − n for all positive integers n . Equivalently, this means that 3 n 3 − n and 5 n 5 − n are integers for all positive integers n . Thus, since we have 3 n 3 + 5 n 5 + b a n to be an integer for all positive integers n (for some positive integers a , b ) we then have n n 3 + n n 5 + b a n − ( 3 n 3 − n + 5 n 5 − n ) = 3 n + 5 n + b a n = 1 5 8 n + b a n = ( 1 5 b 8 b + 1 5 a ) ∗ n to be an integer for all positive integers n .
Using logic similar to Daniel's above in determining the least sum for a + b (we must have 1 5 ∣ b and seek to minimise the value of a from the minimum value of b ), we soon attain a = 7 , b = 1 5 as the pair of integers giving the least value of a + b = 2 2
good solution!!
Slight error that doesn't affect the solution: The fractional part of 5 ( k + 1 ) 5 isn't 5 k 5 + 1 , although the two have the same fractional part, and similarly for 3 ( k + 1 ) 3 .
First of all sorry for using the comments section to post my solution but I have the same problem as Jared. Now with your presumed permission, this is the solution
first take 'n' common out of the expression which yields n(n^4/5 + n^2/4 +a/b) assume some t = n^2. Now, for the expression to stay an integer plug in perfect squares into the new expression in 't'. For eg. for t=1 expr = (8/15 + a/b). Hence again for the expression to stay an integer, a/b = 7/15. Reason for taking a,b as small as possible is to find least value of a+b. Taking t=2 also yields the same result. Hence a+b is always 22.
Sorry again for using wrong space for my solution.
All that you needed was the last little bit after you figured out that f(1) was the smallest value. Refer to my solution.
Let I 1 = 3 n 3 + 5 n 5 + b a n ∈ Z and I 2 = 3 ( n + 1 ) 3 + 5 ( n + 1 ) 5 + b a ( n + 1 ) ∈ Z .
Now, I 2 − I 1 = 3 3 n 2 + 3 n + 1 + 5 5 n 4 + 1 0 n 3 + 1 0 n 2 + 5 n + 1 + b a = ( n 2 + n ) + ( n 4 + 2 n 3 + 2 n 2 + n ) + 3 1 + 5 1 + b a = s o m e i n t e g e r + 1 5 8 + b a ∈ Z
So a + b = 7 + 1 5 = 2 2 . Answer is 2 2
instead put n=1. we get : 1/3 + 1/5 + a/b = some integer ( ...-1,0,1…) integer could be > = 1 as 1/3 + 1/5 + a/b is positive as long as a & b are positive integers. so 1/3 + 1/5 + a/b = 1 ….. assuming that z=1 & thought to try for few more but it worked for first try. a/b = 5+3/5x3 = 8/15. sub a/b in main eqn for n=2 also satisfies it making it an integer. so a + b = 8 + 15 = 22
Could you explain why I 3 is also an integer with your polynomial?
Log in to reply
In fact, he can work with I n and I n + 1 instead of I 1 and I 2 and then apply induction.
Log in to reply
True enough, I misread. However, there is still another problem. If two numbers have a difference that is an integer, they might not necessarily be integers, and so he has to show that 3 1 + 5 1 + 1 5 7 is an integer, which is simple enough.
Isn't this also minimizing a/b a not a and b???
\frac{n^3}{3}
if we let n=5 ,,5^3/3+5^5/5+1X5/15 therefore a=1 b=15 that gives an integer too !!
From n = 1 , we can narrow down the solutions to b = 1 5 , a = 7 + 1 5 k . Since for all n ∈ Z + the addition of 1 5 k is useless to our task of making the expression an integer since it just adds a positive whole number, we can get rid of that, leaving a = 7 , b = 1 5 as the answer which minimizes a + b . Since the problem implies that an answer exists, this is enough justification for an answer of a + b = 2 2 .
But that's boring. Let's first see if that actually works. Subbing in ( 7 , 1 5 ) we come to the polynomial 1 5 3 n 5 + 5 n 3 + 7 n . We have shown in the base case that n = 1 yields an integer. Assume that 1 5 3 k 5 + 5 k 3 + 7 k is an integer, then 1 5 3 ( k + 1 ) 5 + 5 ( k + 1 ) 3 + 7 ( k + 1 ) . The expansion is equal to 1 5 3 k 5 + 5 k 3 + 7 k + k 4 + 2 k 3 + 3 k 2 + 2 k + 1 . Using the inductive step, this is an integer, and we are done. a + b = 2 2 .
So is the argument from the first paragraph still valid enough to affirm this as a minimum? Seems a bit ugly, but I can't find any reason why that wouldn't work
Log in to reply
Not really. For all we know, a = 7 , b = 1 5 might not work for, say, n = 2 , while a = 2 2 , b = 1 5 works for all n .
Log in to reply
But isn't it true as Michael said that the family of possible solutions from the n = 1 case gives a = 7 + 1 5 k , b = 1 5 , and if k > 0 then all we have done is added a positive integer to something that may or may not already be an integer. In this way, it's frivolous to add any k because it just makes the sum larger while not accomplishing anything (a non-integer + integer = non-integer, integer + integer = integer)? The problem doesn't even require that it be a positive integer, just an integer.
Log in to reply
@Mike Kong – Yes, if one relies on the fact that the problem is well posed, then one can argue (as Michael did) that changing k does nothing: if it worked for one k , it would work for all of them, for all n . Whether or not this is a legitimate assumption, is a tricky issue. At the elementary school level, all problems are assumed to be well posed. At the level of professional mathematics, a problem is a theorem to be proved, and you cannot use the fact that the proof exists as part of your proof. It is not possible to draw the line when this switch of attitude occurs, because it is a gradual transition. Which is probably the reason why Michael included the proof that k = 0 works for all n , to make his solution independent on the assumption that the question posed is valid.
Note that, by Euler's Formula: $$n^3\equiv n(\mod 3)$$ and $$n^5\equiv n(\mod 5)$$. We can rewrite the expression as 3 n + 5 n + b a n is an integer of all n . Then we can factor it as $$n\big(\frac{1}{3}+\frac{1}{5}+\frac{a}{b}\big)$$ Since this is an integer, the expression in the bracket must be an integer, as small as possible, which is 1. Solving for a and b , we get a = 7 and b = 1 5 , so a + b = 2 2
You need to minimize a + b and it seems that you minimized b a ,. Can you explain why the minimum occurs when a = 7 and b = 1 5 ?
Log in to reply
I think larger values will increase a and b individually.....I mean if we consider the sum to be 2 or more....
Sorry, I meant Euler's Theorem, not formula.
By Euler's theorem, do you mean the one that
a ϕ ( n ) ≡ 1 ( m o d n ) → a ϕ ( n ) + 1 ≡ a ( m o d n ) ? Your application of this theorem is a very specific case which would best be attributed to Fermat's Little Theorem, that
a p ≡ a ( m o d p ) for prime p .
To determine the smallest possible value of a + b , we choose n = 1 , which makes the equation:
3 1 + 5 1 + b a
= 1 5 b 1 5 a + 8 b
= x [assuming x to be the value of the equation]
For x to be an integer when a + b have the smallest possible value, we calculate the value of a and b such that, x = 1
For this, we need the LCM of 15 and 8, which is 120 [ 1 5 × 8 = 1 2 0 ]
From this LCM, we can see if we put b = 1 5 , x becomes,
x = 1 5 × 1 5 1 5 a + 8 × 1 5
= 1 5 a + 8
So for x to become 1, we put a = 7
and thus, a + b = 7 + 1 5 = 2 2
But how do you know n = 2 or n = 1 8 2 also gives an integer?
Log in to reply
There are a lot of methods for a single problem. I followed this path, and other values of n gives bigger values for a and b
Log in to reply
Well, a and b must make the expression an integer for all n , not just 1.
Using Fermat's Little Theorem: n^5 is congruent to n (modulo 5) and n^3 is congruent to n (modulo 3).
We can rewrite the expression as:
(n^3-n)/3 + (n^5-n)/5 + (an/b + n/3 + n/5)
Factorizing the last term (an/b + n/3 + n/5):
n(a/b + 1/3 + 1/5) = n(a/b + 8/15)
Since we are finding the minimum of a/b for a+b to be minimum, of course, we avoid negativity, a/b = 7/15 for the factor will be at least 1 as its integral factor. Hence, a + b = 22.
Is there no other way to solve this problem? I mean, can we use another simpler theorem?
Log in to reply
let f(n)=n^3/3+n^5/5+an/b. since f(n) takes integral values for all values of n ,f(n+1) must be an integer hence f(n+1)-f(n) is an integer too. f(n+1)-f(n)=((n+1)^3-n^3)/3+ ((n+1)^5-n^5)/5+a/b =n+6n^2+n^4 +2n^3+1/3 + 1/5 +a/b hence 1/3+1/5+a/b should be an integer as all other terms are integers for a+b to be smallest 8/15+a/b=1 a/b=7/15.
let f(n)=n^3/3+n^5/5+an/b. since f(n) takes integral values for all values of n ,f(n+1) must be an integer hence f(n+1)-f(n) is an integer too. f(n+1)-f(n)=((n+1)^3-n^3)/3+ ((n+1)^5-n^5)/5+a/b =n+6n^2+n^4 +2n^3+1/3 + 1/5 +a/b hence 1/3+1/5+a/b should be an integer as all other terms are integers for a+b to be smallest 8/15+a/b=1 a/b=7/15.
let n=1; first two terms sum up to 8/15; therefore, in order to make it an integer last term involving 'a' and 'b' must be 7/15; a+b=7+15=22
consider an integer K ... so k should satisfy the given condition... consider an integer (k+3)... this should also satisfy the condition.... by using above condition for k in condition for (k+3) we get "243/5 + 3a/b" should be integer so if the given condition satisfy for n=1,2and3 and the above obtained condition.... the given will be integer for every integer n.
As per i guessed,I thought the easiest method. If N being an integer then why not put it 1. BY 1 we easily get _\frac{8}{15} + \frac{a}{b}_. Then to make it integer _1_ , \frac{a}{b} has to be equal to \frac{7}{15}. So a= \boxed{7} and b= \boxed{15} THUS a+b = \boxed{22}.
Please check your formatting
1 5 8 + b a . Then to make it integer, b a has to be equal to 1 5 7 . So a = 7 and b = 1 5 THUS a + b = 2 2 .
Problem Loading...
Note Loading...
Set Loading...
Let f ( n ) = 3 n 3 + 5 n 5 + b a n .
For a prime p , ( n + 1 ) p ≡ n p + 1 ( m o d p ) since ( n + 1 ) p = n p + ( 1 p ) n p − 1 + ⋯ + ( p − 1 p ) n + 1 ≡ n p + 1 ( m o d p )
Lemma: If f ( k ) is an integer and f ( 1 ) is an integer, then f ( k + 1 ) is also an integer.
Proof: By our earlier result, the fractional part of 3 ( k + 1 ) 3 is 3 k 3 + 1 and the fractional part of 5 ( k + 1 ) 5 is 5 k 5 + 1 . Then, it suffices to show that 3 k 3 + 1 + 5 k 5 + 1 + b a k + a is an integer. This is 3 k 3 + 1 + 5 k 5 + 1 + b a k + a = 3 k 3 + 3 1 + 5 k 5 + 5 1 + b a k + b a = f ( k ) + 3 1 + 5 1 + b a = f ( k ) + f ( 1 ) which is an integer.
Therefore, we must find a and b such that f ( 1 ) is an integer, and then f ( k ) will be an integer for all positive integer k . f ( 1 ) = 3 1 + 5 1 + b a = 1 5 8 + b a = 1 5 b 8 b + 1 5 a If this is an integer, then 1 5 ∣ 8 b + 1 5 a , and 1 5 ∣ 8 b , so 1 5 ∣ b . To minimize a + b , let b = 1 5 . Then, the minimum a is 7, so the answer is 7 + 1 5 = 2 2 .
Motivation: I was at first unsure of what to do. Then, I thought about induction, since the problem involves every positive integer n . Once I tried to make an inductive argument, the solution followed.