mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-07-08, 16:16   #1
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

1000000001002 Posts
Question Always an integer.



Show that (x^5)/5 + (x^3)/3 +(7x/15) is always an integer for integral values of x ?

Its easy if you know the method.

Similar problems are welcome.

Mally
mfgoode is offline   Reply With Quote
Old 2007-07-08, 17:24   #2
VolMike
 
VolMike's Avatar
 
Jun 2007
Moscow,Russia

7·19 Posts
Default

Well, I don't know the simplest way to reduce this problem, but it can be easy solved with one qiute obviously notice: any integer value can be represented as element of the set {15*k,15*k+1,15*k+2,...,15*k+14} for integer k=0,1,... Thus we can substitute this values for x in out initial expression and get results . Mathematica code, returns values of initial expression by substituting for x:
Code:
  (1/15) x (7 + 5 x^2 + 3 x^4) /. x -> 15*k + Range[0, 14] // Expand
And results:
Code:
  {7 k + 1125 k^3 + 151875 k^5,   1 + 37 k + 675 k^2 + 7875 k^3 + 50625 k^4 + 151875 k^5,   10 + 307 k + 4050 k^2 + 28125 k^3 + 101250 k^4 + 151875 k^5,   59 + 1357 k + 12825 k^2 + 61875 k^3 + 151875 k^4 + 151875 k^5,   228 + 4087 k + 29700 k^2 + 109125 k^3 + 202500 k^4 + 151875 k^5,   669 + 9757 k + 57375 k^2 + 169875 k^3 + 253125 k^4 + 151875 k^5,   1630 + 19987 k + 98550 k^2 + 244125 k^3 + 303750 k^4 + 151875 k^5,   3479 + 36757 k + 155925 k^2 + 331875 k^3 + 354375 k^4 + 151875 k^5,   6728 + 62407 k + 232200 k^2 + 433125 k^3 + 405000 k^4 + 151875 k^5,   12057 + 99637 k + 330075 k^2 + 547875 k^3 + 455625 k^4 + 151875 k^5,   20338 + 151507 k + 452250 k^2 + 676125 k^3 + 506250 k^4 + 151875 k^5,   32659 + 221437 k + 601425 k^2 + 817875 k^3 + 556875 k^4 +    151875 k^5,   50348 + 313207 k + 780300 k^2 + 973125 k^3 + 607500 k^4 + 151875 k^5,   74997 + 430957 k + 991575 k^2 + 1141875 k^3 + 658125 k^4 +    151875 k^5,   108486 + 579187 k + 1237950 k^2 + 1324125 k^3 + 708750 k^4 +    151875 k^5}
As can see, all expression values are integers for integer k. I think there is an shorter solution which uses the same idea, but represents in a brief way (expectedly with usage of properties of modulo operation).

Last fiddled with by VolMike on 2007-07-08 at 17:40
VolMike is offline   Reply With Quote
Old 2007-07-08, 17:27   #3
axn
 
axn's Avatar
 
Jun 2003

484510 Posts
Default

Quote:
Originally Posted by mfgoode View Post
Show that (x^5)/5 + (x^3)/3 +(7x/15) is always an integer for integral values of x

Alternately we need to show that 3x^5 + 5x^3 + 7x is a multiple of 15.

Working modulo 3, we have x^3=x (by Fermat's Little Theorem)
Thus 3x^5 + 5x^3 + 7x == 3x^5 + 5x + 7x == 3x^5 + 12x == 0 (mod 3)

Working modulo 5, we have x^5=x
Thus 3x^5 + 5x^3 + 7x == 3x + 5x^3 + 7x == 10x + 5x^3 == 0 (mod 5)

Thus our expression is divisible by 15, as required.

Q.E.D
axn is offline   Reply With Quote
Old 2007-07-08, 18:35   #4
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

I tried to show 3x^5+5x^3+7x was a multiple of 15
by induction and failed
davieddy is offline   Reply With Quote
Old 2007-07-08, 19:14   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,379 Posts
Default

Proofs by working to a single modulus M are, surely, precisely proofs by induction; just with M distinct base cases and the induction rule being n -> n+M.

But in fact it seems to work for me by straight n->n+1 induction:

3(x+1)^5 = 3x^5 + 15x^4+30x^3+30x^2+15x+3
5(x+1)^3 = 5x^3 + 15x^2 + 15x + 5
7(x+1) = 7x + 7

so the sum is 3x^5 + 5x^3 + 7x (ex hypothesi divisible by 15)
+ lots of things which are in form a multiple of 15
+ 3 + 5 + 7 which equals 15
fivemack is offline   Reply With Quote
Old 2007-07-08, 19:50   #6
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Thanks FiveMack.
Actually I tried to prove that 3x^4 +5x^2 +7
was divisible by 15. This could indeed be false,
when x is a multiple of 3 and/or 5.
David

And THX Mally - a successful puzzle :)
Look forward to the next!

Last fiddled with by davieddy on 2007-07-08 at 20:28
davieddy is offline   Reply With Quote
Old 2007-07-09, 15:52   #7
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Thumbs up Precise and concise!

Quote:
Originally Posted by davieddy View Post
Thanks FiveMack.
Actually I tried to prove that 3x^4 +5x^2 +7
was divisible by 15. This could indeed be false,
when x is a multiple of 3 and/or 5.
David

And THX Mally - a successful puzzle :)
Look forward to the next!


Hold your horses Davie. Here is a precise and concise solution you can ever get. Thats why I put this problem.

Its the type Alpertron and Maxal will appreciate so here it is.

original Expression = [(x^5-x)/5] + [(x^3-x)/3] + x.
But by Fermat's theorem x^5 - x == 0 mod 5 and x^3 -x ==Mod 3 hence the expression is an integer!

Q.E.D

Mally
mfgoode is offline   Reply With Quote
Old 2007-07-09, 19:23   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

145128 Posts
Default

Quote:
Originally Posted by mfgoode View Post
Similar problems are welcome.

Mally
Neat.
Now we can generalize the problem to contain
any number of terms x^p/p where p is prime.
e.g.
x^7/7 +x^2/2 + 5x/14

David
davieddy is offline   Reply With Quote
Old 2007-07-09, 23:49   #9
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by mfgoode View Post
original Expression = [(x^5-x)/5] + [(x^3-x)/3] + x.
For me [(x^n-x)/n] is an integer for any n and x...
since [.] means floor(.) to me...
especially when it is put where it is not needed for anything else like grouping factors of a product or function arguments etc...
m_f_h is offline   Reply With Quote
Old 2007-07-09, 23:58   #10
m_f_h
 
m_f_h's Avatar
 
Feb 2007

1101100002 Posts
Default

Quote:
Originally Posted by davieddy View Post
we can generalize the problem to contain any number of terms x^p/p where p is prime. e.g.
x^7/7 +x^2/2 + 5x/14
or x^11/11+x^101/101+999x/1111...
m_f_h is offline   Reply With Quote
Old 2007-07-12, 08:33   #11
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Thumbs up General Eqn.

Quote:
Originally Posted by davieddy View Post
Neat.
Now we can generalize the problem to contain
any number of terms x^p/p where p is prime.
e.g.
x^7/7 +x^2/2 + 5x/14

David


Excellent Davie!

I would like you to note that the general expression is true for all +ve integers when p is a prime It is also true if p divides x. This is a corollary which results from Fermat’s little theorem.

Thus from your very expression when x is any number e.g. x = 14
14^7/7 + 14^2/2 +5*14/7 an integer although 7 and 2 both divide 14

A more restricted expression can be derived from Fermat’s little theorem, thus
x^6/7 + x^2/3 – 10/21 is also true and always an integer provided the primes
(In denominator) do not divide x , and the constant is changed accordingly as it’s not a function of x but rather of the primes.

Having said that could you derive the general expression in terms of x, p_1, and p_2……?

Try it with x = 5, 11 and any prime.

Mally .
mfgoode is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
k*b^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1 jasong Miscellaneous Math 5 2016-04-24 03:40
Integer factorization? bearnol2 Information & Answers 7 2010-12-09 02:50
Integer factorization with q < 2p mgb Math 36 2009-11-07 15:59
Integer Factorization 2 mgb Math 5 2007-07-23 12:55
Integer FFT nevarcds Math 4 2004-07-28 19:14

All times are UTC. The time now is 20:55.

Sat Jan 23 20:55:06 UTC 2021 up 51 days, 17:06, 0 users, load averages: 1.84, 1.82, 1.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.