MHB Odd Composite Property 1: A Unique Factorization Rule

[yourskadhir]

Hi,

For any odd composite 'N', let u = (N-1)/2, v = u+1, then u^2(mod p) = v^2(mod p) if and only if 'p' is a factor of 'N'.

 

[Deveno]

Re: Odd composite property1

suppose that:

$u^2 \equiv v^2\ (\text{mod }p)$

since $v = u+1$ this is the same as saying:

$0 \equiv 2u + 1\ (\text{mod }p)$

that is:

$2u + 1 = kp$ for some integer $k$.

recalling that $u = \frac{N-1}{2}$, we see that:

$2u + 1 = N = kp$, in which case $p$ divides (is a factor of) $N$.

on the other hand, suppose that $N = kp$.

then:

$u^2 = \frac{N^2 - 2N + 1}{4}$ while:

$v^2 = \left(\frac{N+1}{2}\right)^2 = \frac{N^2 + 2N + 1}{4}$

so:

$v^2 - u^2 = \frac{4N}{4} = N = kp$ thus:

$u^2 \equiv v^2\ (\text{mod }p)$

(it might be instructive to see why p cannot be 2).