Forever integer

Suppose that a a and b b are positive integers, such that for every positive integer n n ,

n 3 3 + n 5 5 + a n b \frac{n^3}{3} + \frac{n^5}{5} + \frac{a n}{b}

is an integer. What is the smallest possible value of a + b a+b ?


The answer is 22.

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.

9 solutions

Daniel Chiu
Dec 8, 2013

Let f ( n ) = n 3 3 + n 5 5 + a n b f(n)=\dfrac{n^3}{3}+\dfrac{n^5}{5}+\dfrac{an}{b} .

For a prime p p , ( n + 1 ) p n p + 1 ( m o d p ) (n+1)^p\equiv n^p+1\pmod p since ( n + 1 ) p = n p + ( p 1 ) n p 1 + + ( p p 1 ) n + 1 n p + 1 ( m o d p ) (n+1)^p=n^p+\dbinom{p}{1}n^{p-1}+\cdots+\dbinom{p}{p-1}n+1\equiv n^p+1\pmod p

Lemma: If f ( k ) f(k) is an integer and f ( 1 ) f(1) is an integer, then f ( k + 1 ) f(k+1) is also an integer.

Proof: By our earlier result, the fractional part of ( k + 1 ) 3 3 \dfrac{(k+1)^3}{3} is k 3 + 1 3 \dfrac{k^3+1}{3} and the fractional part of ( k + 1 ) 5 5 \dfrac{(k+1)^5}{5} is k 5 + 1 5 \dfrac{k^5+1}{5} . Then, it suffices to show that k 3 + 1 3 + k 5 + 1 5 + a k + a b \dfrac{k^3+1}{3}+\dfrac{k^5+1}{5}+\dfrac{ak+a}{b} is an integer. This is k 3 + 1 3 + k 5 + 1 5 + a k + a b = k 3 3 + 1 3 + k 5 5 + 1 5 + a k b + a b = f ( k ) + 1 3 + 1 5 + a b = f ( k ) + f ( 1 ) \begin{aligned} \dfrac{k^3+1}{3}+\dfrac{k^5+1}{5}+\dfrac{ak+a}{b}&=\dfrac{k^3}{3}+\dfrac{1}{3}+\dfrac{k^5}{5}+\dfrac{1}{5}+\dfrac{ak}{b}+\dfrac{a}{b} \\ &=f(k)+\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{a}{b}\\ &=f(k)+f(1) \end{aligned} which is an integer.

Therefore, we must find a a and b b such that f ( 1 ) f(1) is an integer, and then f ( k ) f(k) will be an integer for all positive integer k k . f ( 1 ) = 1 3 + 1 5 + a b = 8 15 + a b = 8 b + 15 a 15 b f(1)=\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{a}{b}=\dfrac{8}{15}+\dfrac{a}{b}=\dfrac{8b+15a}{15b} If this is an integer, then 15 8 b + 15 a 15|8b+15a , and 15 8 b 15|8b , so 15 b 15|b . To minimize a + b a+b , let b = 15 b=15 . Then, the minimum a a is 7, so the answer is 7 + 15 = 22 7+15=\boxed{22} .

Motivation: I was at first unsure of what to do. Then, I thought about induction, since the problem involves every positive integer n n . Once I tried to make an inductive argument, the solution followed.

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 3|n^3-n and 5 n 5 n 5|n^5-n for all positive integers n n . Equivalently, this means that n 3 n 3 \frac{n^3-n}{3} and n 5 n 5 \frac{n^5-n}{5} are integers for all positive integers n n . Thus, since we have n 3 3 + n 5 5 + a n b \frac{n^3}{3}+\frac{n^5}{5}+\frac{an}{b} to be an integer for all positive integers n n (for some positive integers a , b a,b ) we then have n 3 n + n 5 n + a n b ( n 3 n 3 + n 5 n 5 ) = n 3 + n 5 + a n b = 8 n 15 + a n b = ( 8 b + 15 a 15 b ) n \frac{n^3}{n}+\frac{n^5}{n}+\frac{an}{b}-(\frac{n^3-n}{3} + \frac{n^5-n}{5})=\frac{n}{3}+\frac{n}{5}+\frac{an}{b}=\frac{8n}{15}+\frac{an}{b}=(\frac{8b+15a}{15b})*n to be an integer for all positive integers n n .

Using logic similar to Daniel's above in determining the least sum for a + b a+b (we must have 15 b 15|b and seek to minimise the value of a a from the minimum value of b b ), we soon attain a = 7 , b = 15 a=7, b=15 as the pair of integers giving the least value of a + b = 22 a+b=\fbox{22}

Jared Low - 7 years, 6 months ago

good solution!!

KIukiu Ctk - 7 years, 6 months ago

Slight error that doesn't affect the solution: The fractional part of ( k + 1 ) 5 5 \dfrac{(k+1)^5}{5} isn't k 5 + 1 5 \dfrac{k^5+1}{5} , although the two have the same fractional part, and similarly for ( k + 1 ) 3 3 \dfrac{(k+1)^3}{3} .

Daniel Chiu - 7 years, 6 months ago

Log in to reply

Why the downvote?

Daniel Chiu - 7 years, 6 months ago

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.

siddharth shah - 7 years, 6 months ago

All that you needed was the last little bit after you figured out that f(1) was the smallest value. Refer to my solution.

Finn Hulse - 7 years, 4 months ago
Sujoy Roy
Dec 9, 2013

Let I 1 = n 3 3 + n 5 5 + a n b Z I_1=\frac{n^3}{3}+\frac{n^5}{5}+\frac{an}{b} \in \mathbb {Z} and I 2 = ( n + 1 ) 3 3 + ( n + 1 ) 5 5 + a ( n + 1 ) b Z I_2=\frac{(n+1)^3}{3}+\frac{(n+1)^5}{5}+\frac{a(n+1)}{b} \in \mathbb {Z} .

Now, I 2 I 1 = 3 n 2 + 3 n + 1 3 + 5 n 4 + 10 n 3 + 10 n 2 + 5 n + 1 5 + a b = ( n 2 + n ) + ( n 4 + 2 n 3 + 2 n 2 + n ) + 1 3 + 1 5 + a b = s o m e i n t e g e r + 8 15 + a b Z I_2-I_1=\frac{3n^2+3n+1}{3}+\frac{5n^4+10n^3+10n^2+5n+1}{5}+\frac{a}{b}\\ =(n^2+n)+(n^4+2n^3+2n^2+n)+\frac{1}{3}+\frac{1}{5}+\frac{a}{b} \\ =some \: integer+\frac{8}{15}+\frac{a}{b} \in \mathbb {Z}

So a + b = 7 + 15 = 22 a+b=7+15=22 . Answer is 22 \boxed{22}

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

Soham Zemse - 7 years, 6 months ago

Could you explain why I 3 I_3 is also an integer with your polynomial?

Daniel Chiu - 7 years, 6 months ago

Log in to reply

In fact, he can work with I n I_n and I n + 1 I_{n+1} instead of I 1 I_1 and I 2 I_2 and then apply induction.

Jorge Tipe - 7 years, 6 months ago

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 1 3 + 1 5 + 7 15 \dfrac{1}{3}+\dfrac{1}{5}+\dfrac{7}{15} is an integer, which is simple enough.

Daniel Chiu - 7 years, 6 months ago

Isn't this also minimizing a/b a not a and b???

Eddie The Head - 7 years, 6 months ago

\frac{n^3}{3}

Nabil Maani - 7 years, 6 months ago

if we let n=5 ,,5^3/3+5^5/5+1X5/15 therefore a=1 b=15 that gives an integer too !!

Abdelrahman Mostafa - 7 years, 6 months ago
Michael Tong
Dec 8, 2013

From n = 1 n = 1 , we can narrow down the solutions to b = 15 b = 15 , a = 7 + 15 k a = 7 + 15k . Since for all n Z + n \in \mathbb{Z}^+ the addition of 15 k 15k 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 = 15 a = 7, b = 15 as the answer which minimizes a + b a + b . Since the problem implies that an answer exists, this is enough justification for an answer of a + b = 22 a + b = 22 .

But that's boring. Let's first see if that actually works. Subbing in ( 7 , 15 ) (7, 15) we come to the polynomial 3 n 5 + 5 n 3 + 7 n 15 \frac{3n^5 + 5n^3 + 7n}{15} . We have shown in the base case that n = 1 n = 1 yields an integer. Assume that 3 k 5 + 5 k 3 + 7 k 15 \frac {3k^5 + 5k^3 + 7k}{15} is an integer, then 3 ( k + 1 ) 5 + 5 ( k + 1 ) 3 + 7 ( k + 1 ) 15 \frac {3(k + 1)^5 + 5(k+1)^3 + 7(k+1)}{15} . The expansion is equal to 3 k 5 + 5 k 3 + 7 k 15 + k 4 + 2 k 3 + 3 k 2 + 2 k + 1 \frac {3k^5 + 5k^3 + 7k}{15} + k^4 + 2k^3 + 3k^2 + 2k + 1 . Using the inductive step, this is an integer, and we are done. a + b = 22 a + b = \boxed{22} .

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

Mike Kong - 7 years, 6 months ago

Log in to reply

Not really. For all we know, a = 7 , a=7, b = 15 b=15 might not work for, say, n = 2 , n=2, while a = 22 , a=22, b = 15 b=15 works for all n . n.

Alexander Borisov - 7 years, 6 months ago

Log in to reply

But isn't it true as Michael said that the family of possible solutions from the n = 1 n = 1 case gives a = 7 + 15 k , b = 15 a = 7 + 15k, b = 15 , and if k > 0 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 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.

Mike Kong - 7 years, 6 months ago

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 k does nothing: if it worked for one k , k, it would work for all of them, for all n . 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 k=0 works for all n , n, to make his solution independent on the assumption that the question posed is valid.

Alexander Borisov - 7 years, 6 months ago
Edward Jiang
Dec 9, 2013

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 n 3 + n 5 + a n b \frac{n}{3}+\frac{n}{5}+\frac{an}{b} is an integer of all n 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 a and b b , we get a = 7 a=7 and b = 15 b=15 , so a + b = 22 a+b=\boxed{22}

You need to minimize a + b a+b and it seems that you minimized a b \frac{a}{b} ,. Can you explain why the minimum occurs when a = 7 a=7 and b = 15 b=15 ?

Jorge Tipe - 7 years, 6 months ago

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....

Eddie The Head - 7 years, 6 months ago

Sorry, I meant Euler's Theorem, not formula.

Edward Jiang - 7 years, 6 months ago

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 ) a^\phi(n) \equiv 1 \pmod n \rightarrow a^{\phi(n) + 1} \equiv a \pmod 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 ) a^p \equiv a \pmod p for prime p p .

Mike Kong - 7 years, 6 months ago
Tahsin Faruque
Dec 8, 2013

To determine the smallest possible value of a + b a+b , we choose n = 1 n=1 , which makes the equation:

1 3 \frac{1}{3} + + 1 5 \frac{1}{5} + + a b \frac{a}{b}

= 15 a + 8 b 15 b \frac{15a+8b}{15b}

= x x [assuming x x to be the value of the equation]

For x x to be an integer when a + b a+b have the smallest possible value, we calculate the value of a a and b b such that, x = 1 x=1

For this, we need the LCM of 15 and 8, which is 120 [ 15 × 8 = 120 15 \times 8 = 120 ]

From this LCM, we can see if we put b = 15 b=15 , x x becomes,

x = 15 a + 8 × 15 15 × 15 x = \frac{15a + 8 \times 15}{15 \times 15}

= a + 8 15 = \frac{a+8}{15}

So for x x to become 1, we put a = 7 a = 7

and thus, a + b = 7 + 15 = 22 \boxed{a+b = 7+15 = 22}

But how do you know n = 2 n=2 or n = 182 n=182 also gives an integer?

Daniel Chiu - 7 years, 6 months ago

Log in to reply

There are a lot of methods for a single problem. I followed this path, and other values of n n gives bigger values for a a and b b

Tahsin Faruque - 7 years, 6 months ago

Log in to reply

Well, a a and b b must make the expression an integer for all n n , not just 1.

Daniel Chiu - 7 years, 6 months ago

Log in to reply

@Daniel Chiu Thanx for the correction

Tahsin Faruque - 7 years, 6 months ago

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?

Muh. Amin Widyatama - 7 years, 5 months ago

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.

Atharva Gondhalekar - 7 years, 5 months ago

Log in to reply

More understandable. Thanks,

Muh. Amin Widyatama - 7 years, 5 months ago

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.

Atharva Gondhalekar - 7 years, 5 months ago
Bingo Maddy
Dec 12, 2013

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.

Utsav Singhal
Dec 10, 2013

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

Alex Porush - 7 years, 6 months ago

8 15 + a b \frac{8}{15} + \frac{a}{b} . Then to make it integer, a b \frac{a}{b} has to be equal to 7 15 \frac{7}{15} . So a = 7 a= \boxed{7} and b = 15 b= \boxed{15} THUS a + b = 22 a+b = \boxed{22} .

Datu Oen - 7 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...