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

### Like this:

Like Loading...

*Related*

## 9 comments

Comments feed for this article

May 13, 2008 at 7:37 am

TWSo you don’t consider 0 a natural number?

May 13, 2008 at 8:43 am

Vishal LamaSorry 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 Jakobsenis a integer iff is. Since this is an integer iff is. But so and therefore

May 13, 2008 at 12:18 pm

Vishal LamaVery nice, Sune (if that’s your first name)! Your name has been immortalized in the

Problem-Solving Hall of Famepage. 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 ShearerSuppose 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 LamaVery 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 TrinhSorry 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

ThiagarajanA 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