Dividing Prime

Pick any prime number greater than three. Find one less than the square of that prime number. What is the greatest positive integer that must be a divisor of the result?
Source: mathcontest.olemiss.edu 10/10/2011

SOLUTION
Let p be a prime number greater than three. The table below lists the value of p^2-1=\left (p+1\right )\left (p-1\right ) for some prime numbers.

The table suggests that 24 is the greatest positive divisor of p^2-1. The presence of the two consecutive even factors \left (p+1\right ) and \left (p-1\right ) gives us ideas on how to prove the conjecture.
Since 24=2\times 2\times 2\times 3, we want to show that at least three 2s and one 3 come from the product \left (p+1\right )\left (p-1\right )

Idea 1
2\times 2 is easy to see because both \left (p+1\right ) and \left (p-1\right ) are even and each contributes one 2.

Idea 2
If a and b are two consecutive even numbers, then 4 divides either a or b.
Proof
If 4 divides a, we are done.
If 4 does not divide a, then there exist a quotient q and a remainder r such that
a=4q+r,    r=1,2,3
If r=1 or r=3
a=4q+1 or a=4q+3
This is not possible because in either case the right-hand side is an odd number and a is even.
If r=2
a=4q+2
b=a+2
=\left (4q+2\right )+2
=4q+4
=4\left (q+1\right )
The last equation shows that 4 divides b. DONE.

Applying Idea 2
\left (p+1\right ) and \left (p-1\right )
are two consecutive even numbers, thus 4 divides either one of them. So we pick up an additional 2 to have 2\times 2\times 2.

Idea 3
If a,b,c are three consecutive positive integers, then 3 divides one of them.
Proof
If 3 divides a, we are done.
If 3 does not divide a, then there exist a quotient q and a remainder r such that
a=3q+r,    r=1,2
If r=1
a=3q+1
c=a+2
=\left (3q+1\right )+2
=3q+3
=3\left (q+1\right )
The last equation shows that 3 divides c.
If r=2
a=3q+2
b=a+1
=\left (3q+2\right )+1
=3q+3
=3\left (q+1\right )
The last equation shows that 3 divides b. DONE.

Applying Idea 3
\left (p-1\right ),p,\left (p+1\right ) are three consecutive positive integers, thus 3 divides either \left (p-1\right ) or \left (p+1\right ) and not p because it is a prime number. So we pick up a factor 3 to finally have 2\times 2\times 2\times 3.

Therefore, 24 is the greatest positive integer that divides p^2-1.

Answer: Given in solution.

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s