Question

Given prime numbers p and q where p>q, let n=pq and K(n)=(p-1)(q-1)

Also, p+q=n-K(n)+1 and
p-q=sqrt((p+q)^2 -4n)

Prove that if p-q is known, then n can be factored. Given prime numbers p and q where p>q, let n=pq and K(n)=(p-1)(q-1)

Also, p+q=n-K(n)+1 and
p-q=sqrt((p+q)^2 -4n)

Prove that if p-q is known, then n can be factored. @Mathematics

Answer 1

do you know the answer to this? the only thing i know is that what you called K(n) is the same in this case (two primes) as
\[\phi(n)\]the euler totient function

Answer 2

this line
\[p+q=n-K(n)+1\] is an identity

Answer 3

I haven't figured it out yet. They did use that symbol in the question, but I didn't know what it meant.

Answer 4

I was thinking that if p-q = x then you would need to find either p or q in terms of n and x somehow

Answer 5

it is called euler phi function or euler totient function . number of positive integers coprime to n. if n = pq is is (p-1)(q-1)

Answer 6

also i assume this problem is not stated exactly right. it cannot be the case that if all you know is p -q then you know n since for example 11- 7= 4 and 17 - 13 = 4
you must know something else i am sure

Answer 7

well I think you know n and p-q
and you use this to find the p and q

Answer 8

try looking half way down the page here
http://en.wikipedia.org/wiki/Divisor_function

Answer 9

like if n was equal to 6 and p-q was 1then you could use it to find 2 and 3 somehow

Answer 10

i am thinking maybe you know
\[\phi(n)\] and p - q. look here i think this is exactly what you want
http://mathforum.org/library/drmath/view/65461.html

Answer 11

matter of fact it looks exactly like what you have, but i am not sure what you know and what you are trying to find.

Answer 12

yeah, I'm still not really sure I understand what I am trying to find. And I don't really understand what that function does exactly.

Answer 13

http://en.wikipedia.org/wiki/Euler%27s_totient_function
you should make sure you know exactly what you know and what you need to find, but i think the second link i sent has your solution

Answer 14

Ok satallite I think I've got it sort of
\[ p-q=\sqrt{(p+q)^2 -4n}\] then
\[ p+q=\sqrt{(p-q)^2 +4n}\] then
\[ p+q=\sqrt{(p-q)^2 +4n} = n-ϕ(n)+1\]then solve for ϕ(n)
\[ϕ(n) = -\sqrt{(p-q)^2 +4n} +1 +n\]
then you can use the equation the guy on the other forums used
p = (n + 1 - phi(n) + sqrt((n + 1 - phi(n))^2 - 4n))/2
q = (n + 1 - phi(n) - sqrt((n + 1 - phi(n))^2 - 4n))/2

I just don't know how he got those formulas though. Think you could help?

Answer 15

Alright I've got it
let p-q=x
so p=x+q

n=pq
n=(x+q)q
n=q^2 +xq
q^2+xq-n=0
solve with the quadratic formula to get q then sub into p=x+q to get p