Go back to previous page
Forum URL: http://www.cut-the-knot.org/cgi-bin/dcforum/forumctk.cgi
Forum Name: High school
Topic ID: 408
#0, Number theory question
Posted by shivgaur on Mar-20-11 at 11:29 AM
The Problem:
Suppose for a positive integer n both 5n+1 and 7n+1 are perfect squares. Show that n is divisible by 24

My attempt:
Since 5n+1 is a perfect square and n is a positive integer then, the n's for which 5n+1 is a perfect square are: n= 3, 7, 16, 24 ..........
and for 7n+1 : n = 5, 9, 24......
therefore the least common 'n' which makes both 5n+1 and 7n+1 a perfect square is 24 and therefore 'n' is divisible by 24.

Any better approach to this problem?


#1, RE: Number theory question
Posted by alexb on Mar-23-11 at 06:46 PM
In response to message #0
This only says that n = 24 works. It does not prove the general statement.

#2, RE: Number theory question
Posted by shivgaur on Mar-26-11 at 08:35 PM
In response to message #1
Thanks Alex! Got the point. Will try for a general solution.

#3, RE: Number theory question
Posted by mr_homm on Mar-29-11 at 07:20 AM
In response to message #2
A hint:

Try reducing the expressions mod 3 and mod 8. Then, what are all the squares in mod 3 and mod 8? From there, you can work out the details.


#4, RE: Number theory question
Posted by shivgaur on Apr-05-11 at 11:22 AM
In response to message #3
Many thanks! mod 3 and mod 8 works out beautifully!

#5, RE: Number theory question
Posted by mr_homm on Apr-07-11 at 11:54 AM
In response to message #4
You're welcome. I'm glad to hear that. It is sometimes difficult to give just the right amount of hint. Too little and there is frustration, too much and the fun is spoiled.