[Update: I have decided to pose at least one problem (or perhaps, two problems) a week from now and invite solutions to those problems from the readers. This should be exciting. I am sure all of you would want your names to be listed in the Problem-Solving Hall of Fame page! 8) ]
This post is about getting the readers of this blog to participate! And so, let me pose an elementary divisibility problem and invite solutions from the readers. “Elementary” doesn’t necessarily mean “easy”, by the way. It just means elementary methods can be used to solve the problem. I am particularly looking for elegant solutions, though all kinds of solutions are welcome. Readers with correct solutions will be given credit and their names will be included in the Problem-Solving Hall of Fame page on this blog! So, go ahead, write down your solutions.
Problem: Suppose and are two positive natural numbers such that is divisible by . Prove that .
10 comments
Comments feed for this article
May 13, 2008 at 7:37 am
TW
So you don’t consider 0 a natural number?
May 13, 2008 at 8:43 am
Vishal Lama
Sorry about that confusion. I do consider to be a natural number, in which case, the statement of the problem needs to be modified, which I have done now.
May 13, 2008 at 10:08 am
Sune Kristian Jakobsen
is a integer iff is. Since this is an integer iff is. But so and therefore
May 13, 2008 at 12:18 pm
Vishal Lama
Very nice, Sune (if that’s your first name)! Your name has been immortalized in the Problem-Solving Hall of Fame page. Check it out!
Now, I am sure there are others who have alternative solutions. Don’t hide; come out with your elegant solutions! If you experience difficulty writing LaTeX code, don’t worry, I will edit your comments. Writing your solution in plain text will suffice!
May 14, 2008 at 2:57 am
Paul Shearer
Suppose y^2+xy+1 = y(x+y)+1 divides x^2+xy+1 = x(x+y)+1; then there exists a positive natural number k such that k(y(x+y)+1) = x(x+y)+1. Grouping terms and factoring gives
(*) k-1 = (x+y)(x-ky).
Let us consider the cases k = 1 and k > 1 separately.
If k = 1 then k-1 = 0, so one of the factors on the RHS of (*) must be 0. But x+y > 0 so we must have x-ky = 0, giving x = y.
If k > 1 we derive a contradiction. Given k > 1, k-1 > 0 so the RHS terms of (*) must be strictly positive. Thus x-ky > 0 -> x+y > (k+1)y -> (x+y)(x-ky) > (k+1)y > k-1. But k-1 < k+1 < (k+1)y, contradiction.
Therefore k must be 1 and x=y.
May 14, 2008 at 3:39 am
Vishal Lama
Very nice, Paul!
May 14, 2008 at 3:51 pm
Problem of the Week (POW-2) « Todd and Vishal’s blog
[…] Trimble Since the cat’s out of the bag and we’ve had some public discussion of our first Problem of the Week, I thought I’d officially kick things off with a new problem, this time under the ground […]
January 27, 2009 at 3:02 am
Huan Trinh
Sorry for the mess on previous comments. Here goes the solution again: [Edit: Noted!]
x^2+xy+1 is divisible by y^2+xy+1 so if x != y then x > y. Let x = ky + r where 0 <= r < y. Then x^2 + xy + 1 = y^2(k+1)k + yr(2k+1) + r^2 + 1 (1), and y^2 + xy +1 = y^2(k+1) + yr + 1 (2).
(2)/(1) = q = k + { yr(k+1) + r^2 + 1 – k } / (2).
Since yr < y^2 and r^2 = 1, { yr(k+1) + r^2 + 1 – k } 1. We have k + 1 > k – 1, and r >= 1. The left-hand side of (3) is greater than its right-hand side. So k must be 1; and r must be 0 otherwise the left-hand side of (3) is greater than 0. k = 1 and r = 0 means x = y.
December 3, 2009 at 5:22 am
Thiagarajan
A little late..but here is mine
x^2 + xy + 1/y^2 + xy + 1 = n (where n is a integer)
=> x^2 + xy + 1 = ny^2 +nxy + n)
=> x(x+y) + 1 = ny(x+y) + n
=> x(x+y) -ny(x+y) = n-1
=>(x-ny)(x+y) = n-1
which means
((x-ny) == (n-1)) && ((x+y) == (n-1)) = true – (1)
x-ny = n-1
=> x – ny + y – y = n-1
=> (x + y) – y(n-1) = n-1 (rearranging previous statement)
for (1) to be true,y(n-1) = 0
y is not sure as per the given data
=> n-1 = 0 => n = 1
=> x^2 + xy + 1 = y^2 +xy + 1
=> x^2 = y^2 => x = y
Q.E.D
April 13, 2019 at 10:59 am
prof dr mircea orasanu
indeed here are many consequences and more many implications as in ordinary differential equations observed prof dr mircea orasanu and prof drd horia orasanu