1
$\begingroup$

Establish the following test for primes.

If $n$ is odd, greater than $5$, and there exist relatively prime integers $a$ and $b$ such that $a — b = n$ and $a + b = p_1\cdot p_2\cdot... p_k$ (where $p_1, p_2 , . . . , p_k$ are the odd primes less than $\sqrt n$ ), then $n$ is prime.

$\endgroup$
0
2
$\begingroup$

Hint:

Suppose $p_1|n$, then $p_1|(a+b)+(a-b)=2a$ and $p_1|(a+b)-(a-b)=2b$. What can you do using $p_1$ is odd, and what can you do with all other $p_i$s?

$\endgroup$
1
  • $\begingroup$ cool hint, thanx :) $\endgroup$ – Vikram Dec 2 '15 at 7:53
1
$\begingroup$

$a + b = \prod p_i$

$a - b = \prod p_i - 2b = n$. gcd($a,b$) =1 so none of the $p_i$ divide $\prod p_i - 2b = n$ (except maybe 2 but n is odd so that's not possible). But the $p_i$ are all the primes up to the $\sqrt(n)$. So as none of those primes divide n, n is prime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.