A mathematics olympiad problem

In summary, the problem states that if m,k,n are natural numbers and n>1, then we cannot have m(m+1)=kn. Using induction, the problem proves that if m follows this rule... m+1 must follow it .. so (m+1)(m+2) is not expressible in the form of kn. However, I have found a solution to the problem.
  • #1
physics kiddy
135
1
Question is :

If m,k,n are natural numbers and n>1, prove that we cannot have m(m+1)=kn.

My attempt :

Using induction:

If m follows this rule... m+1 must follow it ..
so
(m+1)(m+2) = kn
Since every natural number can be expressed as the product of primes, it follows that (m+1) and (m+2) are primes.
Now, my question is...
are there any two consecutive primes which can be expressed in the form of kn.

Thanks for any help.
 
Last edited:
Physics news on Phys.org
  • #2
physics kiddy said:
Since every natural number can be expressed as the product of primes, it follows that (m+1) and (m+2) are primes.

Why?

Also where have you used the induction step?
 
  • #3
physics kiddy said:
\Since every natural number can be expressed as the product of primes, it follows that (m+1) and (m+2) are primes.
Thanks for any help.

I think you don't understand what is met by "product of primes" . For m = 13, m+1= 14 and m+2 = 15. 14*15 is a product of primes, i.e. 2*3*5*7 but neither 14 or 15 are primes.
 
  • #4
hint: m and (m+1) are relatively prime, so any prime factor of k, divides either m or m+1
 
  • #5
willem2 said:
hint: m and (m+1) are relatively prime, so any prime factor of k, divides either m or m+1

I believe you proved it. Since k divides either of m or m+1, it is not expressible in the form of kn because then it would have to divide both m and m+1.
Is that enough or needs a better proof ?

Thanks for the hint ...
 
  • #6
physics kiddy said:
I believe you proved it. Since k divides either of m or m+1, it is not expressible in the form of kn because then it would have to divide both m and m+1.
Is that enough or needs a better proof ?

Thanks for the hint ...

It isn't that simple. Some of the prime factors of k could divide m, and some of them could divide m+1, but none of them can divide both.

This means that if a prime factor p of k divides m, then p^n has to divide m, so m has to be an n'th power, and so has m+1, but different n'th powers differ by more than one if m>0, so m and m+1 can't be both n'th powers, but we just proved they have to be, producing a contradiction
 
  • #7
The thing to notice is that m and m+1 are relatively prime. This means that the only factor of k which can divide m and m+1 simultaneously is 1. Hence both m and m+1 must be nth powers. This is impossible for n>1.
 
  • #8
I have found a solution to the problem. It was a bit difficult to type, so I wrote it and attached two .jpg files. Let me know if it's correct ...
 

Attachments

  • DSC02186.jpg
    DSC02186.jpg
    16.7 KB · Views: 440
  • DSC02187.jpg
    DSC02187.jpg
    16.8 KB · Views: 398
  • #9
physics kiddy said:
I have found a solution to the problem. It was a bit difficult to type, so I wrote it and attached two .jpg files. Let me know if it's correct ...

Nope. You've proved that k can't be a factor of m. There's no reason why k has to be a factor of m or m+1
 
  • #10
I request you to consider it once again. Let me be clear with it ...
If m(m+1) = k^n, then m(m+1)/k*k ... n = 1
alright upto here ?
Then it's clear that k must divide either m or m+1 but it can't divide both.
I don't believe there's anything wrong with it.
I would like to seek opinion of others (mathsman1963,ramsey) also. If they say it's not upto mark, then I would pick some other step.

Thanks.
 
  • #11
physics kiddy said:
Then it's clear that k must divide either m or m+1 but it can't divide both.

No it's not obvious. Suppose k is the product of two primes, ##k=pq##. Then it's entirely possible that ##p | m## and ##q | m+1##. You need to argue that this is impossible.
 
Last edited:
  • #12
willem2 said:
hint: m and (m+1) are relatively prime, so any prime factor of k, divides either m or m+1

This and other posts by willem2 are very good hints. Note that willem2 said any "prime factor" of k had to divide either m or m+1. You need to give consideration to why willem 2 was so specific. If 10 divides 14*15, there is no reason why 10 must divide both 14 and 15. You need consider what are the prime factors of k and how many times each factor appears in k^n. For instance if k^3 = 3^3 * 7^12 * 2^6 divides m * (m+1) Then at least one of 3^3, 7^12 and 2^6 must divide m and those that don't divide m must divide m+1. Why is this and why is it not possible. You merely need to look at the posts by willem2 to answer this question. You have proven you have what is needed to solve this problem, you just need to put it all together. Please keep trying, and you will get it.
P.S. problems in number theory are interesting in that the details can be put into specific criteria and that there are facts that if properly associated with specific criteria will allow for solutions to more complicated problems. Some problems have proven to be seemingly imposible to solve, but that only makes it more interesting. You have a interest in math. This is good since the world need good mathematicans. In number theory, products of primes, squares, congruences, and powers of numbers are basic building blocks. Once you understand those, there are a whole world of interesting concepts to explorer.
 
  • #13
I now understand what you people want to say ... but I don't find any way to solve the problem that way ...

For example I considered the number 6 = 2 * 3.
Simply, I can say that 2(3) when divided by k = 6 is divisible by k as n = 1 here
but k = (6)^2 can't divide 2(3).

How do I put it in variables. I am new to number theory. Please give a solution this time ... I would certainly try some other on my own some day.
 
  • #14
physics kiddy said:
I now understand what you people want to say ... but I don't find any way to solve the problem that way ...

For example I considered the number 6 = 2 * 3.
Simply, I can say that 2(3) when divided by k = 6 is divisible by k as n = 1 here
but k = (6)^2 can't divide 2(3).

How do I put it in variables. I am new to number theory. Please give a solution this time ... I would certainly try some other on my own some day.
OK I will be as specific as I can. Every number k can be written as a product of primes, say k = (P1)^(i1) * (P2)^(i2)*(P3)^(i3)*...(Pm)^(im) and k^n = (P1)^(i1*n)*(P2)^(i2*n)*...(Pm)^(im*n). Thus the power of each prime is divisible by n. Assume that k^n = m*(m+1). Since m and m+1 are coprime, m must equal (Pj)^(ij*n)*...(Pk)^(ik*n) = (k')^n and m+1 must equal (Pf)^(if*n)*...(Pl)^(il*n). Since each power of the prime factors of m is divisible by n and each power of the prime factors of m+1 are divisible by n, m and m+1 much each be a number to the nth power. Thus we have a proof by contridiction since for n>1 like powers of numbers must differ by more than 1 or we must have m = 0 in which case there are no prime factors.
 
  • #15
say n = 2. then m and m+1 are both squares, which is not likely.
 
  • #16
I got it. Thanks a lot for teaching me something new. Such fabulous proofs of number theory make me a fan of it. I want to master it but don't know where to begin. Please suggest me some books. Thanks again ...
 
  • #17
Last edited by a moderator:

What is a mathematics olympiad problem?

A mathematics olympiad problem is a challenging mathematical question or puzzle that is used in competitions to test the problem-solving abilities of students. These problems often require creative and logical thinking to come up with a solution.

What is the purpose of a mathematics olympiad problem?

The purpose of a mathematics olympiad problem is to encourage students to think critically and develop their problem-solving skills. These problems also help identify talented students in mathematics and foster a love for the subject.

What is the difficulty level of a mathematics olympiad problem?

The difficulty level of a mathematics olympiad problem can vary depending on the competition and the age group of the participants. However, these problems are generally considered to be challenging and require advanced mathematical knowledge and problem-solving techniques.

How can I prepare for a mathematics olympiad problem?

To prepare for a mathematics olympiad problem, you can practice solving similar problems and familiarize yourself with different mathematical concepts and techniques. You can also participate in mock competitions or seek help from a mentor or teacher.

What are the benefits of participating in mathematics olympiad competitions?

Participating in mathematics olympiad competitions can help students improve their critical thinking, problem-solving, and analytical skills. It also provides an opportunity to interact with like-minded individuals and gain recognition for academic achievement.

Similar threads

  • Linear and Abstract Algebra
Replies
8
Views
663
  • Linear and Abstract Algebra
Replies
2
Views
881
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
2K
Replies
4
Views
603
  • Linear and Abstract Algebra
Replies
17
Views
1K
Replies
7
Views
782
  • Linear and Abstract Algebra
Replies
1
Views
862
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
272
Back
Top