My Solution to: Mathematics × Programming Competition #6

While we are waiting for @kenchung to write about the winners to the last competition (https://steemit.com/contest/@kenchung/question-mathematics-programming-competition-6), here is how I solved it! 😼

The problems was:

Given that x is a square number and p is a prime number, and they satisfy the equation x = 1000000007p + 1. Find the sum of all possible values of p.

First, since x is to be a square number, I want to add a new variable, y, defined such that:
y^2 = x

I can now rewrite the probem's formula like this:

y^2 = 1000000007p + 1
y^2 - 1 = 1000000007p
(y + 1)(y - 1) = 1000000007p

y is an integer number and p is prime, 1000000007 is prime too.
Hence, we know that the only possible Integer factorization of 1000000007p is 1000000007 * p (they are already two primes)

Note: we can argue that also 1 and 1000000007p are two numbers that multiplied together give 1000000007p, but then their difference is not 2, so we cannot find y that satisfy the previous equations.

Now, solving:
(y + 1)(y - 1) = 1000000007p
for p, we get only two solutions:

1)

y + 1 = 1000000007
y = 1000000006
p = y - 1 = 1000000005
p = 3×5×66666667

p is not prime, so this is not a valid value for p.

2)

y - 1 = 1000000007
y = 1000000008
p = y + 1 = 1000000009

p is prime!!

So the only solution for the equation is:

p = 1000000009

Did you figure it out?

🐾