Mathematics desk
< April 23	<< Mar \| April \| May >>	April 25 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 24

Primality question

I just gave a test to my students. One of the questions basically came down to "suppose x is prime and y is the least number greater than x such that: 1) x does not divide y; and 2) every number less than x which divides y also divides x. Show that y is prime." I realize that (1) is unnecessary, but this was intended to be an exercise in induction, not number theory. My question is, do we actually need that x is prime? I can't seem to come up with any examples showing that it's necessary, but I haven't looked out too far.--130.195.2.100 (talk) 02:28, 24 April 2012 (UTC)[reply]

After a little thought, my question can be rephrased as: is there a prime p and positive integers a and b with p greater than a and no primes between

p^{b}a

and

p^{b+1}

?--130.195.2.100 (talk) 03:52, 24 April 2012 (UTC)[reply]

Since there is a prime between x and 2x, y must be less than 2x; so y can't have any factors larger than x; y prime if x is is an obvious consequence of this. Suppose

x=p(1)^{a(1)}p(2)^{a(2)}...p(n)^{a(n)}

, then

y=p(1)^{b(1)}p(2)^{b(2)}...p(n)^{b(n)}

with b(k) > a(k) some k or y is prime. If the former, then

c=p(k)^{a(k)+1}|y

, obviously c does not divide x, so c > x must occur; thus,

p(k)>p(1)^{a(1)}...p(k-1)^{a(k-1)}p(k+1)^{a(k+1)}...p(n)^{a(n)}

must hold, so (assume p is increasing) k = n. This gets us to where you are. So, we want to show that there is a, b and prime p with p > a and no primes in

(p^{b}a,p^{b+1})

We can minimize the interval by taking a = p-1, which gives us

(p^{b}(p-1),p^{b+1})

. If you look at our article on Bertrand's Postulate, you'll see that in 2010 Pierre Dusart showed that there is always a prime in the interval

(x,(1+k^{-1})x)

with

k(x)=25ln^{2}x

for large enough x. We can write our interval in the form

(x,(1+(p-1)^{-1})x)

In this case,

k(x)=k(p^{b}a)

, which diverges to infinity with b, so Dusart's interval will be smaller than ours for large enough p, b, and a. Obviously, this doesn't show that y must be prime, but it does show that the size of b's that don't give prime y is limited by p. (there may be a better way to go about this, but it's the best I've got, I'm not really a Number Theorist.) Phoenixia1177 (talk) 08:18, 24 April 2012 (UTC)[reply]

Taking

n=sqrt(p^{b}(p-1))

and assuming Legendre's Conjecture would give a prime q so

p^{b}(p-1)=n^{2}<q<(n+1)^{2}<p^{b+1}

, which would show that y must be prime. Though, the conjecture remains unproven as of yet. Phoenixia1177 (talk) 08:31, 24 April 2012 (UTC)[reply]

To answer the original question, I believe if you remove (1) then you do need that x is prime. Consider, for instance, x=4 and y=8. GromXXVII (talk) 14:51, 24 April 2012 (UTC)[reply]

Removing 1.) doesn't change anything, there is a z satisfying 2.) that is less than 2x, so since x < y <= z, y is to small to be divisible by x. Also, x = 4 has y = 5, not 8; 1 | 5 and 1 | 4. I think you may have misread the question, it is not required that if z | x, then z | y; only that z | y and z < x, then z | x. Phoenixia1177 (talk) 15:42, 24 April 2012 (UTC)[reply]

Your result would also follow from there is always a prime in (kx, (k+1)x) for all x and k; here k = p - 1 and x = p ** b, but that's not proven either. Sorry to just keep saying if this conjecture holds than yes, just trying to be informative.Phoenixia1177 (talk) 19:25, 24 April 2012 (UTC)[reply]

Oops, indeed I didn't see the first phrase. GromXXVII (talk) 19:37, 27 April 2012 (UTC)[reply]

Hmm, sounds like I asked a rather hard problem. A computer search found no counter-examples less than 1 million, although I assume that computer checks have verified Legendre's Conjecture to much further than that. Thanks for the responses.--130.195.2.100 (talk) 01:39, 26 April 2012 (UTC)[reply]

Hungarian Algorithm using matrices

Hi All,

The Hungarian algorithm for the assignment problem, as it is commonly described involves steps like crossing out rows and columns. Is there anyway in which this algorithm can be expressed in terms of canonical matrix operations.

.Gulielmus estavius (talk) 18:22, 24 April 2012 (UTC)[reply]