1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Have you seen this prime number equation?

  1. Jul 6, 2011 #1
    One of my professors told us about a prime number equation he came up with back in his own college days in Russia. It was published in a Russian journal in the problems section years and years ago and has not been translated to English. The thing is, his professor thought this equation must have already been presented somewhere. My professor could not find it anywhere. I can not find it. But it does seem like the kind of thing that should already have been said. So I'm wondering, has anyone seen this equation before?

    an integer p is prime iff there exists a unique m and a unique n (m and n are natural numbers) such that: 1/p = 1/m - 1/n
     
  2. jcsd
  3. Jul 6, 2011 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    I'm not familiar with it.

    To unpack it a little,

    [tex]\frac{1}{p}=\frac{1}{m}-\frac{1}{n}\quad\to\quad p=\frac{n\,m}{n-m}[/tex]

    Added in Edit:

    I did notice the following:

    [tex]\frac{1}{p-1}-\frac{1}{p}=\frac{1}{p^2-p}[/tex]

    So for any prime p, it's easy enough to find m & n:

    m = p - 1

    and

    n = m p = p(p-1).

    Are those (m & n) unique for all primes?
     
    Last edited: Jul 6, 2011
  4. Jul 6, 2011 #3
    Well, m and n depend on each other, so I can say at least that it is a unique pair. And m can be expressed depending only on p, so for each p a unique m. The same for n, it can be expressed in terms of p, so for each p a unique n. So, yes, if I understand the question correctly.
     
  5. Jul 6, 2011 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    The fact is that for any natural number k > 1, it's true that:

    [tex]\frac{1}{k-1}-\frac{1}{k}=\frac{1}{k^2-k}\quad\to\quad\frac{1}{k}=\frac{1}{k-1}-\frac{1}{k^2-k}[/tex]

    So that m = k - 1 and n = k(k-1). According to your professor's conjecture, if k is prime, then n and m are unique. Also, according to the conjecture, if k is not prime, then there must be at least on other pair of natural numbers which give 1/k in the prescribed way.

    It turns out to be easy to show that if k is not prime, then the m, n pair are not unique.
     
  6. Jul 7, 2011 #5
    EDIT: Sorry for the latexfail, my post didn't seem to be compiling right and I was too lazy to figure out why so I just deleted all the latex code.

    Here's a proof that m and n are unique when k is prime:

    ****Spoiler Alert****

    Let m and n be natural numbers such that (1/m) - (1/n) = (1/k), and suppose that k is prime. Rearranging gives

    (1) mn = (n - m)k.

    Let d = gcd(m,n), and suppose that m = da, n = db, where gcd(a,b) = 1. It is well-known that the identity gcd(m,n) * lcm(m,n) = mn holds for all integers m,n; thus, since lcm(m,n) = dab, we can divide the above relation by d to get

    (2) dab = (b - a)k.

    However, since gcd(a,b) = 1, we have gcd(a, b - a) = gcd(b, b - a) = 1. In general, if an integer x divides a product of integers yz with gcd(x,y) = 1, then necessarily x divides z . In this case, it follows that a and b divide k . Since k is assumed prime, we have three cases: Either a = b = k , in which case the right-hand side of (2) vanishes (contradiction); or a = b = 1, which has the same problem; or a = 1, b = k (the sign is wrong if a = k, b = 1 ). Plugging this into (2) gives d = k - 1. Putting things together, we see that m = da = k - 1 and n = db = k(k - 1) = k^2 - k, which is the solution that has already been pointed out. This completes the proof.
     
    Last edited: Jul 7, 2011
  7. Jul 7, 2011 #6

    PAllen

    User Avatar
    Science Advisor
    Gold Member

    I came up with a slightly different proof (really, I think, just different formulation) of the proof that m,n are unique for p prime.

    First, note a few obvious facts from the problem statement (m,n natural numbers):

    n > m
    0 < m < p
    0 < p-m < p
    p = nm / (n-m)
    n = pm / (p - m )

    Considering the last of these formulas, if p-m=1 we have the universal solution m=p-1, n=p(p-1). So we inquire about a case where p-m > 1, thus 1 < p-m < p, and 0 < m < p-1. Since we assume p prime, we must have p-m a factor of m (from last formula). Thus:

    m = k (p-m) [1]

    which gives:

    p = (k+1)m/k

    k and k+1 can only have 1 as common factor (suppose qr=k; smallest possible way to use q as factor of k+1 is q(r+1) = qr + q = k+q > k+1 unless q=1). Therefore k must be a divisor of m (including 1 as possibility). But if m/k > 1, we have a factorization of p. Thus k=m. But this leads, from [1] above, to 1 = p-m, which contradicts our assumption that p-m > 1. QED.

    ---

    Just for completeness, I note that for any p, if ab=p,

    m = p-a
    n = b(p-a)

    is a solution, allowing at least a=1,b=p plus some other solution for p not prime.

    ----

    This is a really cute prime property which is new to me (but then, I never studied any number theory).
     
  8. Jul 10, 2011 #7
    Is there anyway to verify that it hasn't been published elsewhere, or at least be reasonably confident? I mean other than scouring actual paper between bindings. Like, a way to google it or something? My google attempts weren't getting the message across to the system. Perhaps I don't know what syntax would be clear to it.
     
  9. Jul 10, 2011 #8

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    This theorem (or conjecture) doesn't look all that useful to me. After all, for any integer, k>1, letting m = k-1, and n = k(k-1) gives [itex]\displaystyle \frac{1}{k}=\frac{1}{m}-\frac{1}{n}\,.[/itex] Determining whether these are the only values of m & n which give k in this way, seems to be at least as difficult as any other method for check the primality of k.
     
  10. Jul 12, 2011 #9
    I don't think the point is to use it for a prime check. You're right, that would be less than efficient. I think it's just an exploration of primes and falls more toward number theory.
     
  11. Jul 12, 2011 #10

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Well, yes, it is a nice proof to work out in a number theory class.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Have you seen this prime number equation?
  1. Prime number (Replies: 1)

  2. Prime numbers (Replies: 5)

  3. Prime Numbers (Replies: 3)

Loading...