%%Page: 1 1 TeXDict begin HPSdict begin 1 0 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a 0 0 a SDict begin [ /Title () /Subject () /Creator (LaTeX with hyperref package) /Author () /Producer (dvips + Distiller) /Keywords () /DOCINFO pdfmark end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.1) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 800 -4000 a SDict begin [ /Count -0 /Dest (section.1) cvn /Title (Introduction) /OUT pdfmark end 800 -4000 a 800 -4000 a SDict begin [ /Count -0 /Dest (section.2) cvn /Title (Proof of Theorem 1) /OUT pdfmark end 800 -4000 a 800 -4000 a SDict begin [ /Count -0 /Dest (section.3) cvn /Title (Proof of Theorem 2) /OUT pdfmark end 800 -4000 a 800 -4000 a SDict begin [ /Count -0 /Dest (section.4) cvn /Title (Acknowledgements) /OUT pdfmark end 800 -4000 a 800 -4000 a SDict begin [ /Page 1 /View [ /Fit ] /PageMode /UseOutlines /DOCVIEW pdfmark end 800 -4000 a 800 -4000 a SDict begin [ {Catalog} << >> /PUT pdfmark end 800 -4000 a 800 -4000 a SDict begin H.S end 800 -4000 a 800 -4000 a SDict begin 14.5 H.A end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (Doc-Start) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 10800 1172 a @beginspecial 0 @llx 0 @lly 99 @urx 16 @ury 2880 @rwi @setspecial %%BeginDocument: logo129.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: logo128.eps %%Creator: fig2dev Version 3.2.3 Patchlevel %%CreationDate: Thu Nov 8 16:13:04 2001 %%For: pope@fry.research.att.com (Sue Pope) %%BoundingBox: 0 0 99 16 %%Magnification: 0.1500 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save newpath 0 16 moveto 0 0 lineto 99 0 lineto 99 16 lineto closepath clip newpath -12.0 26.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin %%Page: 1 1 10 setmiterlimit 0.00900 0.00900 sc 7.500 slw % Ellipse n 2213 1988 856 856 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr % Ellipse n 2213 1991 813 813 0 360 DrawEllipse gs col8 1.00 shd ef gr gs col8 s gr % Ellipse n 1602 1879 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2001 2575 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2831 1877 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2618 1509 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 1806 1519 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2205 1364 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 1669 2290 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2762 2305 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2439 2579 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2220 1992 440 440 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr % Ellipse n 2618 1509 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1805 1515 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1669 2290 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2205 1360 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2762 2305 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1600 1875 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2439 2579 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2831 1877 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2001 2573 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr /Times-Bold ff 225.00 scf sf 1997 2652 m gs 1 -1 sc (23) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2438 2659 m gs 1 -1 sc (11) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Roman ff 480.00 scf sf 3375 2205 m gs 1 -1 sc (Article 09.3.1) col0 sh gr /Times-Roman ff 480.00 scf sf 3375 1650 m gs 1 -1 sc (Journal of Integer Sequences, Vol. 12 \(2009\),) col0 sh gr /Times-Bold ff 225.00 scf sf 2618 1592 m gs 1 -1 sc (2) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2830 1956 m gs 1 -1 sc (3) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2761 2386 m gs 1 -1 sc (6) dup sw pop 2 div neg 0 rm col0 sh gr % Ellipse n 1805 1517 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Polyline n 2554 1797 m 2554 1796 l 2554 1790 l 2554 1779 l 2554 1765 l 2553 1753 l 2552 1743 l 2550 1736 l 2548 1730 l 2544 1725 l 2540 1721 l 2534 1717 l 2528 1713 l 2521 1711 l 2514 1709 l 2507 1708 l 2499 1707 l 2492 1707 l 2483 1707 l 2474 1707 l 2465 1708 l 2456 1710 l 2447 1712 l 2438 1714 l 2431 1717 l 2423 1720 l 2416 1724 l 2408 1728 l 2401 1734 l 2394 1739 l 2388 1745 l 2382 1751 l 2377 1756 l 2372 1762 l 2368 1768 l 2363 1775 l 2359 1783 l 2356 1791 l 2352 1799 l 2350 1807 l 2348 1814 l 2346 1823 l 2345 1831 l 2345 1841 l 2345 1852 l 2346 1863 l 2349 1873 l 2352 1884 l 2356 1894 l 2360 1902 l 2365 1910 l 2371 1919 l 2378 1928 l 2385 1937 l 2393 1946 l 2401 1955 l 2409 1963 l 2417 1970 l 2425 1977 l 2435 1985 l 2446 1993 l 2457 2000 l 2467 2008 l 2477 2015 l 2487 2021 l 2494 2027 l 2501 2033 l 2506 2038 l 2510 2043 l 2513 2049 l 2515 2055 l 2516 2061 l 2516 2067 l 2516 2073 l 2514 2079 l 2510 2087 l 2505 2095 l 2498 2104 l 2490 2113 l 2481 2120 l 2473 2125 l 2465 2129 l 2458 2131 l 2449 2133 l 2440 2134 l 2431 2134 l 2422 2133 l 2414 2131 l 2406 2128 l 2396 2122 l 2385 2115 l 2375 2107 l 2366 2101 l 2359 2097 l 2353 2096 l 2350 2098 l 2347 2101 l 2346 2107 l 2344 2114 l 2344 2122 l 2344 2130 l 2345 2138 l 2346 2145 l 2347 2151 l 2349 2158 l 2352 2164 l 2355 2169 l 2360 2174 l 2364 2179 l 2370 2182 l 2375 2186 l 2382 2188 l 2390 2190 l 2399 2193 l 2409 2194 l 2419 2195 l 2429 2196 l 2438 2196 l 2448 2196 l 2456 2195 l 2465 2194 l 2475 2192 l 2484 2189 l 2493 2187 l 2501 2183 l 2509 2180 l 2516 2177 l 2524 2172 l 2533 2166 l 2541 2159 l 2548 2152 l 2555 2144 l 2560 2137 l 2565 2129 l 2569 2121 l 2573 2111 l 2576 2102 l 2579 2093 l 2581 2084 l 2583 2076 l 2584 2068 l 2584 2058 l 2584 2049 l 2583 2040 l 2582 2032 l 2580 2023 l 2577 2014 l 2572 2004 l 2568 1994 l 2563 1984 l 2558 1976 l 2552 1968 l 2546 1960 l 2538 1952 l 2531 1945 l 2524 1938 l 2517 1932 l 2509 1926 l 2501 1921 l 2493 1914 l 2484 1908 l 2476 1902 l 2468 1897 l 2461 1890 l 2453 1883 l 2445 1876 l 2437 1869 l 2431 1862 l 2427 1856 l 2423 1849 l 2420 1842 l 2418 1835 l 2417 1830 l 2417 1825 l 2417 1820 l 2417 1816 l 2418 1812 l 2419 1808 l 2419 1806 l 2420 1803 l 2421 1801 l 2422 1798 l 2424 1796 l 2425 1794 l 2427 1792 l 2429 1789 l 2431 1787 l 2433 1785 l 2436 1783 l 2437 1781 l 2439 1780 l 2442 1779 l 2444 1778 l 2446 1778 l 2448 1777 l 2450 1777 l 2452 1777 l 2455 1777 l 2457 1777 l 2460 1776 l 2462 1776 l 2465 1775 l 2468 1775 l 2470 1775 l 2473 1775 l 2476 1775 l 2479 1776 l 2482 1776 l 2484 1777 l 2487 1777 l 2489 1777 l 2492 1778 l 2495 1779 l 2498 1780 l 2502 1782 l 2506 1785 l 2510 1788 l 2514 1790 l 2517 1792 l 2520 1794 l 2522 1795 l 2524 1796 l 2525 1798 l 2527 1799 l 2529 1800 l 2531 1802 l 2534 1805 l 2536 1807 l 2539 1809 l 2540 1811 l 2542 1812 l 2544 1813 l 2546 1814 l 2547 1814 l 2549 1813 l 2550 1811 l 2552 1808 l 2554 1804 l 2555 1801 l 2556 1798 l 2556 1796 l 2557 1795 l 2557 1793 l 2557 1792 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 1871 1753 m 1902 1705 l 2090 1705 l 2075 1753 l 2075 2255 l 2012 2317 l 1933 2317 l 2012 2255 l 2012 1753 l 1871 1753 l 1918 1737 l cp gs 0.00 setgray ef gr gs col0 s gr % Polyline n 2169 1705 m 2278 1705 l 2263 1720 l 2247 1753 l 2247 2129 l 2278 2191 l 2152 2191 l 2169 2176 l 2185 2129 l 2185 2098 l 2185 1753 l cp gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 1600 1877 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr /Times-Bold ff 225.00 scf sf 2197 1439 m gs 1 -1 sc (1) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 1667 2376 m gs 1 -1 sc (47) dup sw pop 2 div neg 0 rm col0 sh gr $F2psEnd rs %%EndDocument @endspecial Black Black 5483 8354 a Fx(On)860 b(P)-72 b(ositiv)g(e)864 b(In)-72 b(tegers)863 b Fw(n)e Fx(with)h(a)e(Certain) 15098 11305 y(Divisibilit)-72 b(y)864 b(Prop)72 b(ert)-72 b(y)22421 16447 y Fv(Florian)520 b(Luca)18164 18440 y(Instituto)g(de)g (Matem\023)-780 b(aticas)11948 20432 y(Univ)-43 b(ersidad)518 b(Nacional)j(Aut\023)-780 b(onoma)521 b(de)f(M)-43 b(\023)-737 b(exico)23126 22425 y(C.P)-130 b(.)519 b(58089)20102 24417 y(Morelia,)h(Mic)-43 b(hoac\023)-780 b(an)24372 26410 y(M)-43 b(\023)-737 b(exico)p 0 1 0 0 TeXcolorcmyk 18597 28402 a SDict begin H.S end 18597 28402 a 0 1 0 0 TeXcolorcmyk Fu (fluca@matmor.unam.mx)p 0 1 0 0 TeXcolorcmyk 35003 27428 a SDict begin H.R end 35003 27428 a 35003 28402 a SDict begin [ /H /I /Border [0 0 0] /Color [0 1 1] /Action << /Subtype /URI /URI (mailto:fluca@matmor.unam.mx) >> /Subtype /Link H.B /ANN pdfmark end 35003 28402 a Black 22031 32388 a Fv(Vicen)-43 b(tiu)519 b(Tipu)17160 34380 y(Departmen)-43 b(t)520 b(of)g(Mathematics)19469 36373 y(Univ)-43 b(ersit)g(y)518 b(of)i(T)-130 b(oron)-43 b(to)14563 38365 y(T)-130 b(oron)-43 b(to,)521 b(On)-43 b(tario,)520 b(Canada)i(M5S)f(2E4)p 0 1 0 0 TeXcolorcmyk 17777 40712 a SDict begin H.S end 17777 40712 a 0 1 0 0 TeXcolorcmyk -354 x Fu(vtipu@math.toronto.edu)p 0 1 0 0 TeXcolorcmyk 35823 39384 a SDict begin H.R end 35823 39384 a 35823 40358 a SDict begin [ /H /I /Border [0 0 0] /Color [0 1 1] /Action << /Subtype /URI /URI (mailto:vtipu@math.toronto.edu) >> /Subtype /Link H.B /ANN pdfmark end 35823 40358 a Black Black Black 24133 44728 a Ft(Abstract)p Black Black 5870 46802 a Fs(In)461 b(this)h(pap)34 b(er,)475 b(w)-34 b(e)461 b(study)h(the)g(p)34 b(ositiv)-34 b(e)461 b(in)-34 b(tegers)461 b Fr(n)g Fs(ha)-34 b(ving)462 b(at)f(least)g(t) -34 b(w)g(o)463 b(distinct)f(prime)4052 48307 y(factors)404 b(suc)-34 b(h)405 b(that)g(the)g(sum)g(of)f(the)h(prime)e(factors)i(of) f Fr(n)g Fs(divides)g(2)36069 47867 y Fq(n)p Fp(\000)p Fo(1)38167 48307 y Fn(\000)269 b Fs(1.)800 50522 y SDict begin H.S end 800 50522 a 800 50522 a SDict begin 14.5 H.A end 800 50522 a 800 50522 a SDict begin [ /View [/XYZ H.V] /Dest (section.1) cvn H.B /DEST pdfmark end 800 50522 a 2200 x Fm(1)2152 b(In)-60 b(tro)60 b(duction)800 55642 y Fl(F)-108 b(or)447 b(ev)-36 b(ery)449 b(p)36 b(ositiv)-36 b(e)449 b(in)-36 b(teger)447 b Fk(n)h Fl(with)g(factorization)i Fk(n)393 b Fl(=)30072 54646 y Fj(Q)31327 56030 y Fq(p)p Fp(j)p Fq(n)32909 55642 y Fk(p)33562 55160 y Fq(a)34062 55271 y Fi(p)34599 55642 y Fl(,)452 b(w)-36 b(e)448 b(put)f Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))393 b(=)44134 54646 y Fj(P)45536 56030 y Fq(p)p Fp(j)p Fq(n)47119 55642 y Fk(p)p Fl(.)621 b(Sev)-36 b(eral)800 57358 y(authors)339 b(ha)-36 b(v)g(e)340 b(considered)f(this)g(function)g(or)h(one)f(of)h (the)f(closely)i(related)f(functions)f Fk(B)67 b Fl(\()p Fk(n)p Fl(\))369 b(=)47764 56362 y Fj(P)49166 57745 y Fq(p)p Fp(j)p Fq(n)50749 57358 y Fk(p)51402 56876 y Fq(a)51902 56987 y Fi(p)52439 57358 y Fl(,)800 59174 y(or)525 b Fk(f)142 b Fl(\()p Fk(n)p Fl(\))524 b(=)7111 58178 y Fj(P)8513 59562 y Fq(p)p Fp(j)p Fq(n)10096 59174 y Fk(a)10779 59373 y Fq(p)11308 59174 y Fk(p)p Fl(,)547 b(or)525 b Fk(\014)15284 59373 y Fq(k)15853 59174 y Fl(\()p Fk(n)p Fl(\))f(=)19701 58178 y Fj(P)21103 59562 y Fq(p)p Fp(j)p Fq(n)22686 59174 y Fk(p)23339 58692 y Fq(k)24432 59174 y Fl(for)h(some)g(\014xed)f(p)36 b(ositiv)-36 b(e)526 b(in)-36 b(teger)524 b Fk(k)45 b Fl(.)852 b(In)524 b(general,)549 b(the)800 60780 y(questions)408 b(studied)e(w)-36 b(ere)407 b(the)g(sets)g(of)h(p)36 b(ositiv)-36 b(e)408 b(in)-36 b(tegers)408 b(satisfying)g(certain)g(algebraic)g(or)f(divisibilit)-36 b(y)800 62385 y(relations)426 b(in)-36 b(v)g(olving)426 b(one)f(of)h(the)e(ab)36 b(o)-36 b(v)g(e)426 b(functions.)575 b(F)-108 b(or)425 b(example,)j(Erd})-650 b(os)424 b(and)h(P)-36 b(omerance)425 b(\([)p 0 .5 0 TeXcolorrgb 48977 62385 a SDict begin H.S end 48977 62385 a 0 .5 0 TeXcolorrgb Fl(9)p 0 .5 0 TeXcolorrgb 49627 61529 a SDict begin H.R end 49627 61529 a 49627 62385 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.ErPom) cvn H.B /ANN pdfmark end 49627 62385 a Black Fl(],)j([)p 0 .5 0 TeXcolorrgb 51138 62385 a SDict begin H.S end 51138 62385 a 0 .5 0 TeXcolorrgb Fl(11)p 0 .5 0 TeXcolorrgb 52439 61529 a SDict begin H.R end 52439 61529 a 52439 62385 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Pom1) cvn H.B /ANN pdfmark end 52439 62385 a Black Fl(])800 63990 y(and)354 b([)p 0 .5 0 TeXcolorrgb 3611 63990 a SDict begin H.S end 3611 63990 a 0 .5 0 TeXcolorrgb Fl(12)p 0 .5 0 TeXcolorrgb 4912 63134 a SDict begin H.R end 4912 63134 a 4912 63990 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Pom2) cvn H.B /ANN pdfmark end 4912 63990 a Black Fl(]\))h(studied)e(the)h(set)h(of)g(p)36 b(ositiv)-36 b(e)355 b(in)-36 b(tegers)355 b Fk(n)f Fl(suc)-36 b(h)354 b(that)g Fk(f)142 b Fl(\()p Fk(n)p Fl(\))369 b(=)g Fk(f)142 b Fl(\()p Fk(n)134 b Fl(+)g(1\),)370 b(referred)354 b(to)g(as)h Fh(R)-33 b(uth-)800 65595 y(A)-66 b(ar)g(on)536 b(numb)-66 b(ers)p Fl(.)814 b(De)512 b(Koninc)-36 b(k)513 b(and)f(Luca)g([)p 0 .5 0 TeXcolorrgb 24189 65595 a SDict begin H.S end 24189 65595 a 0 .5 0 TeXcolorrgb Fl(6)p 0 .5 0 TeXcolorrgb 24839 64739 a SDict begin H.R end 24839 64739 a 24839 65595 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.KoLu1) cvn H.B /ANN pdfmark end 24839 65595 a Black Fl(,)p 0 .5 0 TeXcolorrgb 25713 65595 a SDict begin H.S end 25713 65595 a 0 .5 0 TeXcolorrgb Fl(7)p 0 .5 0 TeXcolorrgb 26363 64739 a SDict begin H.R end 26363 64739 a 26363 65595 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.KoLu2) cvn H.B /ANN pdfmark end 26363 65595 a Black Fl(])h(studied)e(p)36 b(ositiv)-36 b(e)513 b(in)-36 b(tegers)512 b Fk(n)h Fl(with)g(at)f(least)h(t)-36 b(w)g(o)800 67200 y(distinct)461 b(prime)g(factors)h(for)f(whic)-36 b(h)461 b Fk(\014)20004 67399 y Fq(k)20574 67200 y Fl(\()p Fk(n)p Fl(\))g(divides)g Fk(n)p Fl(.)662 b(De)462 b(Koninc)-36 b(k)461 b(and)g(Luca)g([)p 0 .5 0 TeXcolorrgb 42361 67200 a SDict begin H.S end 42361 67200 a 0 .5 0 TeXcolorrgb Fl(8)p 0 .5 0 TeXcolorrgb 43011 66344 a SDict begin H.R end 43011 66344 a 43011 67200 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.KoLu3) cvn H.B /ANN pdfmark end 43011 67200 a Black Fl(])h(studied)e(p)36 b(ositiv)-36 b(e)p Black 26475 70521 a(1)p Black eop end end %%Page: 2 2 TeXDict begin HPSdict begin 2 1 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.2) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 1328 x Fl(in)-36 b(tegers)406 b Fk(n)h Fl(with)f(at)g(least)h(t)-36 b(w)g(o)407 b(distinct)e(prime)h(factors)h (suc)-36 b(h)406 b(that)f Fk(B)67 b Fl(\()p Fk(n)p Fl(\))370 b(=)e Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))42137 -3154 y Fo(2)42663 -2672 y Fl(,)412 b(while)407 b(Banks)g(and)800 -1067 y(Luca)433 b([)p 0 .5 0 TeXcolorrgb 4358 -1067 a SDict begin H.S end 4358 -1067 a 0 .5 0 TeXcolorrgb Fl(3)p 0 .5 0 TeXcolorrgb 5009 -1923 a SDict begin H.R end 5009 -1923 a 5009 -1067 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.BaLu) cvn H.B /ANN pdfmark end 5009 -1067 a Black Fl(])h(studied)e(p)36 b(ositiv)-36 b(e)435 b(in)-36 b(tegers)433 b Fk(n)h Fl(suc)-36 b(h)433 b(that)g Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b Fg(j)g Fl(2)31303 -1549 y Fq(n)32225 -1067 y Fg(\000)295 b Fl(1.)2751 539 y(Here,)661 b(w)-36 b(e)616 b(add)f(to)h(the)f(literature)g(on)g(this)h(topic)f(and)g (study)g(p)36 b(ositiv)-36 b(e)617 b(in)-36 b(tegers)615 b Fk(n)h Fl(suc)-36 b(h)614 b(that)800 2144 y Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b Fg(j)g Fl(2)5153 1662 y Fq(n)p Fp(\000)p Fo(1)7277 2144 y Fg(\000)295 b Fl(1.)579 b(Note)434 b(that)f(if)h Fk(n)370 b Fl(=)e Fk(p)434 b Fl(is)f(an)h(o)36 b(dd)433 b(prime,)h(then)17988 5077 y Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b(=)f Fk(p)h Fg(j)g Fl(2)24743 4529 y Fq(p)p Fp(\000)p Fo(1)26770 5077 y Fg(\000)295 b Fl(1)370 b(=)e(2)31148 4529 y Fq(n)p Fp(\000)p Fo(1)33272 5077 y Fg(\000)296 b Fl(1)p Fk(:)800 8011 y Fl(In)340 b(particular,)358 b(b)-36 b(y)340 b(the)f(Prime)h(Num) -36 b(b)36 b(er)339 b(Theorem,)359 b(there)339 b(are)h(at)g(least)h Fk(\031)48 b Fl(\()p Fk(x)p Fl(\))368 b Fg(\030)h Fk(x=)221 b Fl(log)241 b Fk(x)340 b Fl(suc)-36 b(h)339 b(p)36 b(ositiv)-36 b(e)800 9616 y(in)g(tegers)527 b Fk(n)g Fl(not)f(exceeding)h Fk(x)g Fl(as)g Fk(x)h Fg(!)g(1)p Fl(.)858 b(Hence,)550 b(to)527 b(mak)-36 b(e)527 b(our)g(problem)f(more)h(in)-36 b(teresting,)550 b(w)-36 b(e)800 11221 y(lo)36 b(ok)435 b(at)f(the)f(set)14201 12826 y Ff(B)370 b Fl(=)e Fg(f)p Fk(n)434 b Fl(is)g(not)f(a)h(prime)g(and)f Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b Fg(j)g Fl(2)34271 12277 y Fq(n)p Fp(\000)p Fo(1)36395 12826 y Fg(\000)295 b Fl(1)p Fg(g)p Fk(:)800 15150 y Fl(F)-108 b(or)397 b(an)-36 b(y)398 b(subset)e Fg(A)h Fl(of)i(p)36 b(ositiv)-36 b(e)398 b(in)-36 b(tegers)397 b(and)g(a)h(p)36 b(ositiv)-36 b(e)398 b(real)g(n)-36 b(um)g(b)36 b(er)396 b Fk(x)i Fl(w)-36 b(e)398 b(put)e Fg(A)p Fl(\()p Fk(x)p Fl(\))368 b(=)h Fg(A)221 b(\\)g Fl([1)p Fk(;)g(x)p Fl(].)800 16756 y(Our)443 b(\014rst)f(result)h(sho) -36 b(ws)444 b(that)f(the)g(coun)-36 b(ting)443 b(function)g(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))g(is)h(of)g(a)g(smaller)g(order)f(of)i (magnitude)800 18361 y(then)433 b(the)g(coun)-36 b(ting)433 b(function)g(of)h(the)f(primes.)800 18619 y SDict begin H.S end 800 18619 a 800 18619 a SDict begin 14.5 H.A end 800 18619 a 800 18619 a SDict begin [ /View [/XYZ H.V] /Dest (prop.1) cvn H.B /DEST pdfmark end 800 18619 a Black 2454 x Fe(Theorem)499 b(1.)p Black 554 w Fh(The)465 b(estimate)e Fl(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))369 b(=)g Fk(o)p Fl(\()p Fk(x=)221 b Fl(log)241 b Fk(x)p Fl(\))465 b Fh(holds)h(as)f Fk(x)370 b Fg(!)f(1)p Fh(.)2751 23785 y Fl(Th)-36 b(us,)433 b(if)i(a)f(\\random")f(n)-36 b(um)g(b)36 b(er)432 b Fk(n)i Fl(satis\014es)g Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b Fg(j)g Fl(2)29840 23303 y Fq(n)p Fp(\000)p Fo(1)31964 23785 y Fg(\000)295 b Fl(1,)435 b(then)d(it)i(is)g(lik)-36 b(ely)435 b(to)f(b)36 b(e)433 b(a)h(prime.)2751 25390 y(Observ)-36 b(e)402 b(that)f(if)i Fk(n)369 b Fl(=)g Fk(p)14839 24908 y Fq(k)15810 25390 y Fl(is)402 b(a)g(p)36 b(o)-36 b(w)g(er)402 b(of)h(an)f(o)36 b(dd)402 b(prime)g(\(of)g(exp)36 b(onen)-36 b(t)402 b Fk(>)368 b Fl(1\),)409 b(then)401 b Fk(n)370 b Fg(2)e Ff(B)p Fl(.)568 b(Th)-36 b(us,)800 26995 y(again)558 b(b)-36 b(y)557 b(the)g(Prime)g(Num)-36 b(b)36 b(er)556 b(Theorem,)588 b(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))579 b Fg(\025)30010 25999 y Fj(P)31412 27382 y Fq(k)24 b Fp(\025)p Fo(2)33404 26995 y Fk(\031)48 b Fl(\()p Fk(x)35435 26513 y Fo(1)p Fq(=k)36945 26995 y Fl(\))579 b Fg(\025)g Fl(\(2)380 b(+)e Fk(o)p Fl(\(1\)\))p Fk(x)46100 26513 y Fo(1)p Fq(=)p Fo(2)47567 26995 y Fk(=)221 b Fl(log)241 b Fk(x)558 b Fl(as)800 28600 y Fk(x)369 b Fg(!)g(1)p Fl(.)567 b(A)397 b(quic)-36 b(k)397 b(computation)f(with)h(Mathematica) g(rev)-36 b(ealed)397 b(that)f Ff(B)p Fl(\(10)39761 28118 y Fo(6)40288 28600 y Fl(\))g(has)h(3871)h(elemen)-36 b(ts)396 b(of)800 30205 y(whic)-36 b(h)384 b(only)h(236)g(are)g(prime)f (p)36 b(o)-36 b(w)g(ers.)562 b(So,)394 b(one)384 b(w)-36 b(ould)384 b(guess)h(that)f(the)f(main)i(con)-36 b(tribution)383 b(to)h(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))800 31810 y(should)490 b(not)g(come)h(from)g(prime)g(p)36 b(o)-36 b(w)g(ers)490 b(for)h(large)h Fk(x)p Fl(.)749 b(Our)490 b(next)g(result)h(sho)-36 b(ws)490 b(that)h(this)f(is)h(indeed)800 33415 y(so.)800 33415 y SDict begin H.S end 800 33415 a 800 33415 a SDict begin 14.5 H.A end 800 33415 a 800 33415 a SDict begin [ /View [/XYZ H.V] /Dest (prop.2) cvn H.B /DEST pdfmark end 800 33415 a Black 2712 x Fe(Theorem)499 b(2.)p Black 554 w Fh(The)465 b(estimate)e Ff(B)p Fl(\()p Fk(x)p Fl(\))369 b(=)g Fk(x)22101 35645 y Fo(1+)p Fq(o)p Fo(\(1\))25481 36127 y Fh(holds)466 b(as)f Fk(x)369 b Fg(!)h(1)p Fh(.)2751 38839 y Fl(Our)411 b(pro)36 b(ofs)412 b(of)g(b)36 b(oth)411 b(Theorem)p 0 .5 0 TeXcolorrgb 19268 38839 a SDict begin H.S end 19268 38839 a 0 .5 0 TeXcolorrgb Fl(1)p 0 .5 0 TeXcolorrgb 19918 37983 a SDict begin H.R end 19918 37983 a 19918 38839 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (prop.1) cvn H.B /ANN pdfmark end 19918 38839 a Black 412 w Fl(and)p 0 .5 0 TeXcolorrgb 22837 38839 a SDict begin H.S end 22837 38839 a 0 .5 0 TeXcolorrgb Fl(2)p 0 .5 0 TeXcolorrgb 23487 37983 a SDict begin H.R end 23487 37983 a 23487 38839 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (prop.2) cvn H.B /ANN pdfmark end 23487 38839 a Black 412 w Fl(are)h(e\013ectiv)-36 b(e)412 b(in)f(that)g(in)h(b)36 b(oth)411 b(cases)h(sp)36 b(eci\014c)411 b(functions)800 40444 y(b)36 b(ounding)386 b(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))i(from)g(ab)36 b(o)-36 b(v)g(e)388 b(and)e(from)i(b)36 b(elo)-36 b(w)388 b(and)f(whic)-36 b(h)387 b(ha)-36 b(v)g(e)388 b(the)f(indicated)g(orders)g(of)h(magni-)800 42050 y(tude)419 b(are)h(pro)-36 b(vided.)573 b(In)420 b(fact,)k(for)c(Theorem)p 0 .5 0 TeXcolorrgb 23730 42050 a SDict begin H.S end 23730 42050 a 0 .5 0 TeXcolorrgb Fl(2)p 0 .5 0 TeXcolorrgb 24380 41193 a SDict begin H.R end 24380 41193 a 24380 42050 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (prop.2) cvn H.B /ANN pdfmark end 24380 42050 a Black Fl(,)j(w)-36 b(e)420 b(sho)-36 b(w)420 b(that)g(there)f(are)h(at)g(least)g Fk(x)43886 41567 y Fo(1+)p Fq(o)p Fo(\(1\))47221 42050 y Fh(squar)-66 b(efr)g(e)g(e)800 43655 y Fl(n)-36 b(um)g(b)36 b(ers)492 b(in)i Ff(B)p Fl(\()p Fk(x)p Fl(\))g(as)g Fk(x)472 b Fg(!)g(1)p Fl(.)759 b(W)-108 b(e)494 b(c)-36 b(ho)36 b(ose)494 b(not)g(to)g(b)36 b(e)493 b(to)36 b(o)495 b(sp)36 b(eci\014c)494 b(in)f(the)h(ab)36 b(o)-36 b(v)g(e)494 b(statemen)-36 b(ts)493 b(in)800 45260 y(order)433 b(not)h(to)f (complicate)i(the)e(exp)36 b(osition.)2751 46865 y(Throughout)468 b(this)g(pap)36 b(er,)477 b(w)-36 b(e)469 b(use)f(the)g(Landau)g(sym) -36 b(b)36 b(ols)469 b Fk(O)505 b Fl(and)468 b Fk(o)h Fl(as)g(w)-36 b(ell)469 b(as)g(the)f(Vinogrado)-36 b(v)800 48470 y(sym)g(b)36 b(ols)453 b Fg(\035)f Fl(and)f Fg(\034)i Fl(with)f(the)f(usual)h(meanings.)633 b(The)452 b(constan)-36 b(ts)452 b(implied)g(b)-36 b(y)452 b(the)f(sym)-36 b(b)36 b(ols)453 b Fk(O)36 b(;)1074 b Fg(\035)800 50075 y Fl(and)499 b Fg(\034)h Fl(are)f(absolute.)776 b(W)-108 b(e)499 b(recall)h(that)f Fk(U)620 b Fl(=)481 b Fk(O)36 b Fl(\()p Fk(V)289 b Fl(\),)516 b Fk(U)620 b Fg(\034)481 b Fk(V)789 b Fl(and)498 b Fk(V)771 b Fg(\035)481 b Fk(U)638 b Fl(are)500 b(all)g(equiv)-72 b(alen)-36 b(t)500 b(to)800 51680 y(the)511 b(statemen)-36 b(t)510 b(that)h Fg(j)p Fk(U)139 b Fg(j)501 b Fk(<)g(cV)800 b Fl(holds)511 b(with)g(some)h(p)36 b(ositiv)-36 b(e)512 b(constan)-36 b(t)510 b Fk(c)p Fl(,)531 b(while)512 b Fk(U)640 b Fl(=)501 b Fk(o)p Fl(\()p Fk(V)289 b Fl(\))511 b(means)800 53285 y(that)506 b Fk(U)66 b(=V)784 b Fg(!)494 b Fl(0.)798 b(W)-108 b(e)507 b(write)g Fk(c)16733 53484 y Fo(1)17259 53285 y Fk(;)728 b(c)18908 53484 y Fo(2)19434 53285 y Fk(;)950 b(:)221 b(:)g(:)508 b Fl(for)f(p)36 b(ositiv)-36 b(e)508 b(constan)-36 b(ts)506 b(whic)-36 b(h)507 b(are)g(lab)36 b(eled)507 b(increasingly)800 54890 y(throughout)432 b(the)h(pap)36 b(er.)800 57150 y SDict begin H.S end 800 57150 a 800 57150 a SDict begin 14.5 H.A end 800 57150 a 800 57150 a SDict begin [ /View [/XYZ H.V] /Dest (section.2) cvn H.B /DEST pdfmark end 800 57150 a 2177 x Fm(2)2152 b(Pro)60 b(of)716 b(of)h(Theorem)p 0 .5 0 TeXcolorrgb 21536 59327 a SDict begin H.S end 21536 59327 a 0 .5 0 TeXcolorrgb Fm(1)p 0 .5 0 TeXcolorrgb 22612 58095 a SDict begin H.R end 22612 58095 a 22612 59327 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (prop.1) cvn H.B /ANN pdfmark end 22612 59327 a Black 800 62248 a Fl(In)463 b([)p 0 .5 0 TeXcolorrgb 2816 62248 a SDict begin H.S end 2816 62248 a 0 .5 0 TeXcolorrgb Fl(3)p 0 .5 0 TeXcolorrgb 3467 61392 a SDict begin H.R end 3467 61392 a 3467 62248 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.BaLu) cvn H.B /ANN pdfmark end 3467 62248 a Black Fl(],)471 b(it)463 b(w)-36 b(as)464 b(sho)-36 b(wn)463 b(that)g(the)f(coun)-36 b(ting)463 b(function)g(of)h(the)e(set)h(p)36 b(ositiv)-36 b(e)464 b(in)-36 b(tegers)464 b Fk(n)419 b Fg(\024)h Fk(x)463 b Fl(suc)-36 b(h)462 b(that)800 63853 y Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))430 b Fg(j)g Fl(2)5275 63371 y Fq(n)6221 63853 y Fg(\000)320 b Fl(1)469 b(is)h Fk(O)36 b Fl(\()p Fk(x)221 b Fl(log)241 b(log)f Fk(x=)221 b Fl(log)242 b Fk(x)p Fl(\).)685 b(Here,)479 b(w)-36 b(e)470 b(follo)-36 b(w)471 b(the)e(basic)h(approac)-36 b(h)468 b(of)j([)p 0 .5 0 TeXcolorrgb 44446 63853 a SDict begin H.S end 44446 63853 a 0 .5 0 TeXcolorrgb Fl(3)p 0 .5 0 TeXcolorrgb 45096 62997 a SDict begin H.R end 45096 62997 a 45096 63853 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.BaLu) cvn H.B /ANN pdfmark end 45096 63853 a Black Fl(],)479 b(except)469 b(that)800 65458 y(w)-36 b(e)460 b(bring)g(in)g(new)f(argumen)-36 b(ts)460 b(since)g(w)-36 b(e)460 b(w)-36 b(an)g(t)460 b(an)f(upp)36 b(er)459 b(b)36 b(ound)459 b(of)i(a)f(smaller)g(order)g(of)h(magnitude)800 67063 y(than)442 b Fk(x=)221 b Fl(log)241 b Fk(x)p Fl(.)604 b(First,)445 b(some)d(notations.)605 b(Giv)-36 b(en)442 b(a)g(p)36 b(ositiv)-36 b(e)443 b(in)-36 b(teger)442 b Fk(n)p Fl(,)j(w)-36 b(e)443 b(write)g Fk(P)564 b Fl(=)384 b Fk(P)181 b Fl(\()p Fk(n)p Fl(\))442 b(for)h(the)p Black 26475 70521 a(2)p Black eop end end %%Page: 3 3 TeXDict begin HPSdict begin 3 2 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.3) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 1328 x Fl(largest)523 b(prime)f(factor)h(of)f Fk(n)h Fl(and)e Fk(Q)f Fl(=)g Fk(Q)p Fl(\()p Fk(n)p Fl(\))i(for)h(the)e (largest)i(prime)f(factor)h(of)f Fk(\014)74 b Fl(\()p Fk(n)p Fl(\).)844 b(If)523 b Fk(n)g Fl(is)f(o)36 b(dd,)800 -1067 y(w)-36 b(e)452 b(write)g Fk(t)p Fl(\()p Fk(n)p Fl(\))f(for)h(the)f(order)g(of)i(2)e(mo)36 b(dulo)452 b Fk(n)p Fl(;)461 b(that)451 b(is,)457 b(the)451 b(smallest)h(p)36 b(ositiv)-36 b(e)453 b(in)-36 b(teger)451 b Fk(k)497 b Fl(suc)-36 b(h)450 b(that)800 539 y(2)1450 56 y Fq(k)2388 539 y Fg(\021)369 b Fl(1)591 b(\(mo)36 b(d)443 b Fk(n)p Fl(\).)571 b(Finally)-108 b(,)417 b(w)-36 b(e)413 b(write)f Fk(!)48 b Fl(\()p Fk(n)p Fl(\))412 b(and)g(\012\()p Fk(n)p Fl(\))g(for)h(the)e(n)-36 b(um)g(b)36 b(er)411 b(of)i(prime)f(and)f (prime)h(p)36 b(o)-36 b(w)g(er)800 2144 y(divisors)434 b(of)h Fk(n)f Fl(\(of)g(exp)36 b(onen)-36 b(t)433 b Fg(\025)369 b Fl(1\),)434 b(resp)36 b(ectiv)-36 b(ely)-108 b(.)2751 3749 y(W)g(e)475 b(let)g Fk(x)g Fl(b)36 b(e)475 b(a)g(large)h(p)36 b(ositiv)-36 b(e)476 b(n)-36 b(um)g(b)36 b(er.)701 b(W)-108 b(e)474 b(let)i Fk(\013)448 b(>)439 b(\014)513 b Fg(\025)440 b Fk(\015)546 b Fl(b)36 b(e)475 b(n)-36 b(um)g(b)36 b(ers)473 b(in)i(\(0)p Fk(;)221 b Fl(1\).)704 b(Let)474 b Fk(y)48 b(;)697 b(z)800 5354 y Fl(and)433 b(\012)h(b)36 b(e)433 b(functions)h(of)g Fk(x)g Fl(of)g(gro)-36 b(wth)7500 8002 y Fk(y)417 b Fl(=)369 b(exp)12140 6926 y Fj(\000)12749 8002 y Fl(\(log)240 b Fk(x)p Fl(\))16401 7453 y Fq(\013)p Fo(+)p Fq(o)p Fo(\(1\))19450 6926 y Fj(\001)20280 8002 y Fk(;)1523 b(z)428 b Fl(=)369 b(exp)26785 6926 y Fj(\000)27394 8002 y Fl(\(log)240 b Fk(x)p Fl(\))31046 7453 y Fq(\014)46 b Fo(+)p Fq(o)p Fo(\(1\))34064 6926 y Fj(\001)34894 8002 y Fk(;)1522 b Fl(\012)370 b(=)e(\(log)241 b Fk(x)p Fl(\))43119 7453 y Fq(\015)52 b Fo(+)p Fq(o)p Fo(\(1\))800 10650 y Fl(as)413 b Fk(x)369 b Fg(!)g(1)p Fl(.)572 b(W)-108 b(e)412 b(shall)h(mak)-36 b(e)412 b(these)g(functions)g(more)g(precise) g(later.)572 b(W)-108 b(e)412 b(split)g(the)g(set)g Ff(B)p Fl(\()p Fk(x)p Fl(\))g(in)-36 b(to)412 b(six)800 12255 y(subsets)433 b(as)h(follo)-36 b(ws:)8214 14903 y Ff(B)9388 15102 y Fo(1)11021 14903 y Fl(=)1107 b Fg(f)p Fk(n)369 b Fg(2)g Ff(B)p Fl(\()p Fk(x)p Fl(\))g(:)g Fk(P)550 b Fg(\024)369 b Fk(y)48 b Fg(g)p Fl(;)8214 16840 y Ff(B)9388 17039 y Fo(2)11021 16840 y Fl(=)1107 b Fg(f)p Fk(n)369 b Fg(2)g Ff(B)p Fl(\()p Fk(x)p Fl(\))p Fg(n)p Ff(B)20967 17039 y Fo(1)21862 16840 y Fl(:)g Fk(p)23245 16292 y Fo(2)24140 16840 y Fg(j)g Fk(n)434 b Fl(for)g(some)g(prime)f Fk(p)369 b Fg(\025)g Fk(y)48 b Fg(g)p Fl(;)8214 18777 y Ff(B)9388 18976 y Fo(3)11021 18777 y Fl(=)1107 b Fg(f)p Fk(n)369 b Fg(2)g Ff(B)p Fl(\()p Fk(x)p Fl(\))p Fg(n)p Fl(\()p Ff(B)21473 18976 y Fo(1)22294 18777 y Fg([)295 b Ff(B)24649 18976 y Fo(2)25175 18777 y Fl(\))369 b(:)g(\012\()p Fk(n)p Fl(\))g Fg(\025)h Fl(\012)p Fg(g)p Fl(;)8214 20715 y Ff(B)9388 20914 y Fo(4)11021 20715 y Fl(=)1107 b Fg(f)p Fk(n)369 b Fg(2)g Ff(B)p Fl(\()p Fk(x)p Fl(\))p Fg(n)p Fl(\()p Fg([)21185 20166 y Fo(3)21185 21043 y Fq(j)51 b Fo(=1)22874 20715 y Ff(B)24048 20914 y Fq(j)24535 20715 y Fl(\))369 b(:)g Fk(Q)g Fg(\024)g Fk(z)59 b Fg(g)p Fl(;)8214 22871 y Ff(B)9388 23070 y Fo(5)11021 22871 y Fl(=)1107 b Fg(f)p Fk(n)369 b Fg(2)g Fl(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))p Fg(n)p Fl(\()p Fg([)22269 22322 y Fo(4)22269 23199 y Fq(j)51 b Fo(=1)23958 22871 y Ff(B)25132 23070 y Fq(j)25619 22871 y Fl(\))369 b(:)g Fk(t)p Fl(\()p Fk(Q)p Fl(\))f Fg(\025)h Fk(Q)32536 22322 y Fo(1)p Fq(=)p Fo(3)34437 22871 y Fl(and)433 b(\012\()p Fk(t)p Fl(\()p Fk(Q)p Fl(\)\))368 b Fg(\024)i Fl(\012)p Fg(g)p Fl(;)8214 24933 y Ff(B)9388 25132 y Fo(6)11021 24933 y Fl(=)1107 b Ff(B)p Fl(\()p Fk(x)p Fl(\))p Fg(n)p Fl(\()p Fg([)18121 24385 y Fo(5)18121 25261 y Fq(j)51 b Fo(=1)19810 24933 y Ff(B)20984 25132 y Fq(j)21471 24933 y Fl(\))p Fk(:)800 27581 y Fl(W)-108 b(e)434 b(no)-36 b(w)433 b(b)36 b(ound)433 b(the)g(cardinalities)h(of)g (eac)-36 b(h)434 b(of)g(the)f(sets)h Ff(B)31152 27780 y Fq(i)31961 27581 y Fl(for)g Fk(i)369 b Fl(=)g(1)p Fk(;)221 b(:)g(:)g(:)j(;)d Fl(6.)2751 29186 y Fe(The)598 b(set)g Ff(B)9524 29385 y Fo(1)10050 29186 y Fl(.)838 b(Num)-36 b(b)36 b(ers)519 b(in)g Ff(B)19647 29385 y Fo(1)20694 29186 y Fl(are)h(called)g Fk(y)48 b Fh(-smo)-66 b(oth)p Fl(.)838 b(W)-108 b(ell-kno)-36 b(wn)520 b(results)g(concerning)g(the) 800 30791 y(n)-36 b(um)g(b)36 b(er)432 b(of)i Fk(y)48 b Fl(-smo)36 b(oth)433 b(n)-36 b(um)g(b)36 b(ers)432 b Fk(n)370 b Fg(\024)f Fk(x)434 b Fl(\(see)f([)p 0 .5 0 TeXcolorrgb 24661 30791 a SDict begin H.S end 24661 30791 a 0 .5 0 TeXcolorrgb Fl(5)p 0 .5 0 TeXcolorrgb 25312 29935 a SDict begin H.R end 25312 29935 a 25312 30791 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.CEP) cvn H.B /ANN pdfmark end 25312 30791 a Black Fl(]\))g(sho)-36 b(w)434 b(that)f(in)h(our)f(range)h(the)f(estimate)21896 33439 y(#)p Ff(B)24154 33638 y Fo(1)25049 33439 y Fl(=)369 b Fk(xu)27909 32891 y Fp(\000)p Fq(u)p Fo(+)p Fq(o)p Fo(\()p Fq(u)p Fo(\))800 36087 y Fl(holds)433 b(as)h Fk(u)370 b Fg(!)f(1)p Fl(,)434 b(where)g Fk(u)369 b Fl(=)g(log)240 b Fk(x=)221 b Fl(log)241 b Fk(y)482 b Fl(\(=)368 b(\(log)240 b Fk(x)p Fl(\))29045 35605 y Fo(1)p Fp(\000)p Fq(\013)p Fo(+)p Fq(o)p Fo(\(1\))33730 36087 y Fl(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(\).)579 b(Th)-36 b(us,)44562 34482 y SDict begin H.S end 44562 34482 a 44562 34482 a SDict begin 14.5 H.A end 44562 34482 a 44562 34482 a SDict begin [ /View [/XYZ H.V] /Dest (equation.1) cvn H.B /DEST pdfmark end 44562 34482 a 13102 38735 a Fl(#)p Ff(B)15360 38934 y Fo(1)16255 38735 y Fg(\024)369 b Fk(x)221 b Fl(exp)q(\()p Fg(\000)p Fl(\(1)295 b(+)g Fk(o)p Fl(\(1\)\))p Fk(u)221 b Fl(log)241 b Fk(u)p Fl(\))2602 b(as)434 b Fk(x)369 b Fg(!)g(1)p Fk(:)10641 b Fl(\(1\))2751 41383 y Fe(The)643 b(set)h Ff(B)9615 41582 y Fo(2)10141 41383 y Fe(.)956 b Fl(If)560 b Fk(p)583 b Fg(2)g Fl([)p Fk(y)48 b(;)221 b(x)18007 40901 y Fo(1)p Fq(=)p Fo(2)19475 41383 y Fl(])560 b(is)f(a)h(\014xed)g(prime,)591 b(then)558 b(there)h(are)h Fg(b)p Fk(x=p)41977 40901 y Fo(2)42503 41383 y Fg(c)584 b(\024)g Fk(x=p)47336 40901 y Fo(2)48421 41383 y Fl(p)36 b(ositiv)-36 b(e)800 42988 y(in)g(tegers)434 b Fk(n)369 b Fg(\024)g Fk(x)434 b Fl(divisible)g(b)-36 b(y)434 b Fk(p)16894 42506 y Fo(2)17419 42988 y Fl(.)579 b(Summing)432 b(up)h(o)-36 b(v)g(er)434 b(all)h(the)e(p)36 b(ossible)434 b(v)-72 b(alues)434 b(for)g Fk(p)p Fl(,)f(w)-36 b(e)434 b(get)g(that)51947 41383 y SDict begin H.S end 51947 41383 a 51947 41383 a SDict begin 14.5 H.A end 51947 41383 a 51947 41383 a SDict begin [ /View [/XYZ H.V] /Dest (equation.2) cvn H.B /DEST pdfmark end 51947 41383 a 12946 46239 a Fl(#)p Ff(B)15204 46438 y Fo(2)16099 46239 y Fg(\024)18669 44977 y Fj(X)17501 47951 y Fq(y)32 b Fp(\024)p Fq(p)p Fp(\024)p Fq(x)20466 47689 y Fd(1)p Fi(=)p Fd(2)22330 45341 y Fk(x)p 22110 45934 1179 54 v 22110 47150 a(p)22763 46767 y Fo(2)23791 46239 y Fg(\024)369 b Fk(x)26225 44977 y Fj(X)26153 47783 y Fq(y)32 b Fp(\024)p Fq(m)29075 45341 y Fl(1)p 28569 45934 1664 54 v 28569 47150 a Fk(m)29707 46767 y Fo(2)30734 46239 y Fg(\024)369 b Fk(x)33096 44431 y Fj(Z)34425 44782 y Fp(1)33835 47438 y Fq(y)32 b Fp(\000)p Fo(1)35943 45341 y Fk(dt)p 35943 45934 1146 54 v 36281 47150 a(t)37591 46239 y Fg(\034)39421 45341 y Fk(x)p 39421 45934 740 54 v 39450 47150 a(y)40293 46239 y(:)10484 b Fl(\(2\))2751 50406 y Fe(The)499 b(set)f Ff(B)9325 50605 y Fo(3)9851 50406 y Fe(.)578 b Fl(Lemma)434 b(13)g(in)f([)p 0 .5 0 TeXcolorrgb 19099 50406 a SDict begin H.S end 19099 50406 a 0 .5 0 TeXcolorrgb Fl(10)p 0 .5 0 TeXcolorrgb 20400 49550 a SDict begin H.R end 20400 49550 a 20400 50406 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.LuPo) cvn H.B /ANN pdfmark end 20400 50406 a Black Fl(])h(sho)-36 b(ws)434 b(that)f(uniformly)h(for)h(all)f(in)-36 b(tegers)433 b Fk(k)415 b Fg(\025)369 b Fl(1)434 b(w)-36 b(e)433 b(ha)-36 b(v)g(e)50770 48801 y SDict begin H.S end 50770 48801 a 50770 48801 a SDict begin 14.5 H.A end 50770 48801 a 50770 48801 a SDict begin [ /View [/XYZ H.V] /Dest (equation.3) cvn H.B /DEST pdfmark end 50770 48801 a 21897 52451 a Fj(X)21940 55257 y Fq(n)p Fp(\024)p Fq(x)21243 56190 y Fo(\012\()p Fq(n)p Fo(\))p Fp(\025)p Fq(k)24692 53712 y Fl(1)369 b Fg(\034)27541 52814 y Fk(k)45 b(x)221 b Fl(log)241 b Fk(x)p 27541 53407 4323 54 v 29093 54624 a Fl(2)29743 54240 y Fq(k)31996 53712 y Fk(:)18781 b Fl(\(3\))800 58694 y(Applying)434 b(this)f(with)h Fk(k)414 b Fl(=)368 b Fg(b)p Fl(\012)p Fg(c)p Fl(,)435 b(w)-36 b(e)434 b(get)g(that)24221 57089 y SDict begin H.S end 24221 57089 a 24221 57089 a SDict begin 14.5 H.A end 24221 57089 a 24221 57089 a SDict begin [ /View [/XYZ H.V] /Dest (equation.4) cvn H.B /DEST pdfmark end 24221 57089 a 13262 61342 a Fl(#)p Ff(B)15520 61541 y Fo(3)16415 61342 y Fg(\024)369 b Fk(x)221 b Fl(exp)h(\()p Fg(\000)p Fl(\(log)241 b(2)295 b(+)g Fk(o)p Fl(\(1\)\)\012\))2823 b(as)434 b Fk(x)369 b Fg(!)g(1)p Fk(:)10801 b Fl(\(4\))2751 63990 y(F)-108 b(rom)553 b(no)-36 b(w)554 b(on)f(un)-36 b(til)553 b(the)g(end)f(of)j(the)d(argumen)-36 b(t,)583 b(w)-36 b(e)554 b(consider)f Fk(n)574 b Fg(2)e Ff(B)p Fl(\()p Fk(x)p Fl(\))p Fg(n)p Fl(\()p Fg([)44466 63508 y Fo(3)44466 64318 y Fq(j)51 b Fo(=1)46155 63990 y Ff(B)47329 64189 y Fq(j)47816 63990 y Fl(\).)938 b(W)-108 b(rite)800 65595 y Fk(n)453 b Fl(=)f Fk(P)181 b(m)482 b Fl(and)h(observ)-36 b(e)482 b(that)h Fk(P)181 b Fl(\()p Fk(m)p Fl(\))452 b Fk(<)g(P)663 b Fl(and)482 b(that)h Fk(y)500 b Fg(\024)453 b Fk(P)633 b Fg(\024)453 b Fk(x=m)p Fl(.)726 b(Th)-36 b(us,)494 b Fk(m)453 b Fg(\024)f Fk(x=y)48 b Fl(.)726 b(Note)483 b(also)800 67200 y(that)433 b Fk(m)369 b Fg(\025)g Fl(2)434 b(since)f Fk(n)h Fl(is)g(not)g(prime.)p Black 26475 70521 a(3)p Black eop end end %%Page: 4 4 TeXDict begin HPSdict begin 4 3 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.4) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 2751 -2672 a Fe(The)619 b(set)f Ff(B)9565 -2473 y Fo(4)10091 -2672 y Fe(.)892 b Fl(Let)537 b(us)h(\014x)g(a)g(p) 36 b(ositiv)-36 b(e)539 b(in)-36 b(teger)538 b Fk(m)546 b Fg(\024)h Fk(x=y)48 b Fl(.)892 b(Note)539 b(that)e Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))547 b(=)f Fk(P)i Fl(+)365 b Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))546 b Fk(<)800 -1067 y(P)181 b Fl(\012\()p Fk(n)p Fl(\))369 b Fk(<)g(x)p Fl(\012)p Fk(=m)305 b Fl(and)f(that)f(if)i Fk(m)f Fl(is)h(\014xed)f(and)g Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))304 b(is)g(kno)-36 b(wn,)331 b(then)303 b Fk(P)550 b Fl(=)369 b Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))31 b Fg(\000)g Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))304 b(is)g(determined)800 539 y(uniquely;)419 b(th)-36 b(us,)414 b Fk(n)c Fl(is)h(also)g(determined)e(uniquely)-108 b(.)570 b(Since)410 b Fk(n)369 b Fg(2)g Ff(B)34061 738 y Fo(4)34587 539 y Fl(,)415 b(it)410 b(follo)-36 b(ws)412 b(that)e Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b Fg(\024)g Fk(x)p Fl(\012)p Fk(=m)411 b Fl(is)800 2144 y(a)418 b Fk(z)59 b Fl(-smo)36 b(oth)418 b(n)-36 b(um)g(b)36 b(er.)571 b(As)418 b(in)f(the)g(argumen)-36 b(t)417 b(for)h Ff(B)27355 2343 y Fo(1)27881 2144 y Fl(,)j(it)d(follo)-36 b(ws)420 b(from)e(the)f(results)g(from)h([)p 0 .5 0 TeXcolorrgb 47015 2144 a SDict begin H.S end 47015 2144 a 0 .5 0 TeXcolorrgb Fl(5)p 0 .5 0 TeXcolorrgb 47665 1288 a SDict begin H.R end 47665 1288 a 47665 2144 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.CEP) cvn H.B /ANN pdfmark end 47665 2144 a Black Fl(])g(that)f(for)800 3749 y(a)434 b(\014xed)f Fk(m)p Fl(,)h(the)f(n)-36 b(um)g(b)36 b(er)432 b(of)i(p)36 b(ossibilities)435 b(for)f Fk(n)g Fl(is)22015 6774 y Fg(\024)23550 5875 y Fk(x)p Fl(\012)p 23550 6468 1679 54 v 23821 7685 a Fk(m)25362 6774 y(v)26039 6225 y Fp(\000)p Fq(v)27229 6336 y Fi(m)28010 6225 y Fo(+)p Fq(o)p Fo(\()p Fq(v)30021 6336 y Fi(m)30802 6225 y Fo(\))25991 7102 y Fq(m)31224 6774 y Fk(;)800 9642 y Fl(as)350 b Fk(v)2942 9841 y Fq(m)4198 9642 y Fg(!)370 b(1)p Fl(,)d(where)349 b Fk(v)12254 9841 y Fq(m)13511 9642 y Fl(=)368 b(log)19 b(\()p Fk(x)p Fl(\012)p Fk(=m)p Fl(\))p Fk(=)221 b Fl(log)242 b Fk(z)59 b Fl(.)551 b(Since)349 b Fk(x=m)369 b Fg(\025)g Fk(y)48 b Fl(,)367 b(w)-36 b(e)350 b(get)f(that)h Fk(v)41696 9841 y Fq(m)42952 9642 y Fg(\025)369 b Fk(v)417 b Fl(=)368 b(log)241 b Fk(y)48 b(=)221 b Fl(log)241 b Fk(z)800 11247 y Fl(\(=)420 b(\(log)240 b Fk(x)p Fl(\))6390 10765 y Fq(\013)p Fp(\000)p Fq(\014)46 b Fo(+)p Fq(o)p Fo(\(1\))11207 11247 y Fl(as)464 b Fk(x)420 b Fg(!)h(1)p Fl(\).)668 b(Th)-36 b(us,)471 b(for)464 b(large)h Fk(x)p Fl(,)471 b(it)464 b(follo)-36 b(ws)465 b(that)e(uniformly)i(in)e Fk(m)420 b Fg(\024)g Fk(x=y)48 b Fl(,)472 b(the)800 12852 y(n)-36 b(um)g(b)36 b(er)432 b(of)i(p)36 b(ossibilities)435 b(for)f Fk(n)370 b Fg(2)e Ff(B)19570 13051 y Fo(4)20530 12852 y Fl(is)18757 15541 y Fg(\024)20491 14642 y Fk(x)p 20292 15235 1138 54 v 20292 16452 a(m)21784 15541 y Fl(exp\()p Fg(\000)p Fl(\(1)296 b(+)e Fk(o)p Fl(\(1\)\))p Fk(v)269 b Fl(log)241 b Fk(v)48 b Fl(\))800 18409 y(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(.)579 b(Summing)433 b(up)g(no)-36 b(w)433 b(o)-36 b(v)g(er)434 b(all)h(the)e(p)36 b(ossible)434 b(v)-72 b(alues)434 b(for)g Fk(m)369 b Fg(\024)g Fk(x=y)48 b Fl(,)434 b(w)-36 b(e)434 b(get)g(that)13720 21456 y(#)p Ff(B)15978 21655 y Fo(4)17611 21456 y Fg(\024)1107 b Fk(x)221 b Fl(exp)q(\()p Fg(\000)p Fl(\(1)295 b(+)g Fk(o)p Fl(\(1\)\))p Fk(v)269 b Fl(log)240 b Fk(v)48 b Fl(\))35164 20194 y Fj(X)33992 23072 y Fo(2)p Fp(\024)p Fq(m)p Fp(\024)p Fq(x=y)38853 20557 y Fl(1)p 38609 21150 V 38609 22367 a Fk(m)17611 24865 y Fg(\024)1107 b Fk(x)p Fl(\(log)240 b Fk(x)p Fl(\))221 b(exp)q(\()p Fg(\000)p Fl(\(1)295 b(+)g Fk(o)p Fl(\(1\)\))p Fk(v)269 b Fl(log)240 b Fk(v)48 b Fl(\))800 27320 y(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(,)435 b(whic)-36 b(h)433 b(implies)h(that)18280 25715 y SDict begin H.S end 18280 25715 a 18280 25715 a SDict begin 14.5 H.A end 18280 25715 a 18280 25715 a SDict begin [ /View [/XYZ H.V] /Dest (equation.5) cvn H.B /DEST pdfmark end 18280 25715 a 17513 29775 a Fl(#)p Ff(B)19771 29974 y Fo(4)20666 29775 y Fg(\024)369 b Fk(x)221 b Fl(exp)q(\()p Fg(\000)p Fl(\(1)295 b(+)g Fk(o)p Fl(\(1\)\))p Fk(v)269 b Fl(log)240 b Fk(v)48 b Fl(\))15050 b(\(5\))800 32230 y(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(.)2751 33835 y Fe(The)642 b(set)g Ff(B)9612 34034 y Fo(5)10138 33835 y Fe(.)953 b Fl(This)559 b(is)g(b)-36 b(y)558 b(far)h(the)f(most)h(in)-36 b(teresting)558 b(set.)953 b(W)-108 b(e)559 b(\014x)f(again)i Fk(m)581 b Fg(\024)h Fk(x=y)48 b Fl(.)953 b(Since)800 35440 y Fk(Q)506 b Fg(j)g Fk(\014)74 b Fl(\()p Fk(n)p Fl(\),)535 b(w)-36 b(e)514 b(ha)-36 b(v)g(e)515 b(that)e Fk(P)687 b Fg(\021)507 b(\000)p Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))589 b(\(mo)36 b(d)443 b Fk(Q)p Fl(\).)820 b(F)-108 b(urther,)533 b(since)514 b Fk(Q)506 b Fg(j)g Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))506 b Fg(j)g Fl(2)43962 34958 y Fq(n)p Fp(\000)p Fo(1)46141 35440 y Fg(\000)351 b Fl(1,)534 b(w)-36 b(e)515 b(get)800 37045 y(that)483 b Fk(n)330 b Fg(\000)f Fl(1)455 b Fg(\021)f Fl(0)591 b(\(mo)36 b(d)442 b Fk(t)p Fl(\()p Fk(Q)p Fl(\)\),)496 b(so)484 b Fk(P)181 b(m)454 b Fg(\021)g Fl(1)591 b(\(mo)36 b(d)442 b Fk(t)p Fl(\()p Fk(Q)p Fl(\)\).)728 b(By)484 b(the)f(Chinese)g(Remainder)h(Theorem)800 38650 y(\(note)369 b(that)g Fk(t)p Fl(\()p Fk(Q)p Fl(\))g Fg(j)f Fk(Q)164 b Fg(\000)g Fl(1,)384 b(so)370 b Fk(t)p Fl(\()p Fk(Q)p Fl(\))f(and)g Fk(Q)g Fl(are)h(coprime\),)382 b(it)370 b(follo)-36 b(ws)371 b(that)e Fk(P)551 b Fl(is)369 b(uniquely)h (determined)800 40255 y(mo)36 b(dulo)425 b Fk(Qt)p Fl(\()p Fk(Q)p Fl(\).)575 b(The)425 b(n)-36 b(um)g(b)36 b(er)423 b(of)j(suc)-36 b(h)424 b(p)36 b(ossibilities)426 b(for)f Fk(P)550 b Fg(\024)369 b Fk(x=m)425 b Fl(\(without)g(ev)-36 b(en)425 b(accoun)-36 b(ting)424 b(for)800 41860 y(the)433 b(fact)h(that)f Fk(P)615 b Fl(is)434 b(prime\))f(is)16683 40255 y SDict begin H.S end 16683 40255 a 16683 40255 a SDict begin 14.5 H.A end 16683 40255 a 16683 40255 a SDict begin [ /View [/XYZ H.V] /Dest (equation.6) cvn H.B /DEST pdfmark end 16683 40255 a 22320 43774 a Fg(\024)369 b Fl(1)295 b(+)28077 42875 y Fk(x)p 26107 43468 4680 54 v 26107 44685 a(mQt)p Fl(\()p Fk(Q)p Fl(\))30919 43774 y Fk(:)19858 b Fl(\(6\))800 46638 y(W)-108 b(e)445 b(no)-36 b(w)446 b(distinguish)f(sev)-36 b(eral)446 b(cases)g(according)f(to)h(the)f (size)g(of)h Fk(Qt)p Fl(\()p Fk(Q)p Fl(\))f(v)-36 b(ersus)445 b Fk(x=m)p Fl(.)614 b(W)-108 b(e)445 b(also)i(write)800 48243 y Fk(d)369 b Fl(=)f Fk(t)p Fl(\()p Fk(Q)p Fl(\).)578 b(Note)434 b(that)f Fk(d)369 b Fl(=)g Fk(t)p Fl(\()p Fk(Q)p Fl(\))f Fg(\025)h Fk(Q)20375 47761 y Fo(1)p Fq(=)p Fo(3)22211 48243 y Fk(>)g(z)24255 47761 y Fo(1)p Fq(=)p Fo(3)25722 48243 y Fl(.)2751 49848 y Fe(Case)378 b(1.)543 b Fk(Qt)p Fl(\()p Fk(Q)p Fl(\))369 b Fg(\024)g Fk(x=m)p Fl(.)544 b(Let)327 b(us)h(write)h Ff(B)24836 50047 y Fo(5)p Fq(;)p Fo(1)26422 49848 y Fl(for)g(the)e(subset)h(of)h Ff(B)36872 50047 y Fo(5)37726 49848 y Fl(formed)f(b)-36 b(y)328 b(suc)-36 b(h)328 b(n)-36 b(um)g(b)36 b(ers)326 b Fk(n)p Fl(.)800 51453 y(In)446 b(this)f(instance,)450 b(the)445 b(second)h(term)f(in)h(equation)g(\()p 0 .5 0 TeXcolorrgb 27370 51453 a SDict begin H.S end 27370 51453 a 0 .5 0 TeXcolorrgb Fl(6)p 0 .5 0 TeXcolorrgb 28020 50597 a SDict begin H.R end 28020 50597 a 28020 51453 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.6) cvn H.B /ANN pdfmark end 28020 51453 a Black Fl(\))g(dominates)g(and)g(the)f(n)-36 b(um)g(b)36 b(er)444 b(of)j(p)36 b(ossibilities)800 53059 y(for)434 b Fk(P)615 b Fl(when)433 b Fk(m)g Fl(and)g Fk(Q)h Fl(are)g(\014xed)f(is)23446 55182 y Fg(\024)26626 54284 y Fl(2)p Fk(x)p 24981 54877 4680 54 v 24981 56093 a(mQt)p Fl(\()p Fk(Q)p Fl(\))29793 55182 y Fk(:)800 58047 y Fl(Fix)533 b Fk(d)538 b Fl(=)g Fk(t)p Fl(\()p Fk(Q)p Fl(\))532 b(and)g(sum)g(up)g(the)g(ab)36 b(o)-36 b(v)g(e)534 b(b)36 b(ound)531 b(o)-36 b(v)g(er)534 b(all)f(primes)g Fk(Q)g Fl(suc)-36 b(h)532 b(that)g Fk(t)p Fl(\()p Fk(Q)p Fl(\))537 b(=)h Fk(d)p Fl(.)875 b(Since)800 59652 y Fk(Q)369 b Fg(\021)g Fl(1)591 b(\(mo)36 b(d)443 b Fk(d)p Fl(\),)402 b(it)395 b(follo)-36 b(ws)396 b(that)f Fk(Q)369 b Fl(=)f(1)216 b(+)g Fk(d`)395 b Fl(for)g(some)g(p)36 b(ositiv)-36 b(e)395 b(in)-36 b(teger)395 b Fk(`)369 b Fg(\024)g Fk(x)p Fl(\012)p Fk(=)p Fl(\()p Fk(md)p Fl(\))g Fk(<)g(x)p Fl(\012)395 b(\(the)800 61257 y(case)470 b Fk(`)431 b Fl(=)g(0)470 b(is)g(not)g(accepted)f(since)h Fk(Q)431 b Fl(=)f(1)471 b(is)f(not)g(prime\).)686 b(Th)-36 b(us,)479 b(the)470 b(n)-36 b(um)g(b)36 b(er)468 b(of)i(p)36 b(ossibilities)471 b(for)800 62862 y Fk(n)369 b Fg(2)g Ff(B)4374 63061 y Fo(5)p Fq(;)p Fo(1)6065 62862 y Fl(when)434 b Fk(m)f Fl(and)g Fk(d)g Fl(are)h(\014xed)f(do)36 b(es)434 b(not)f(exceed)14483 65116 y(2)p Fk(x)p 14270 65709 1814 54 v 14270 66926 a(md)17243 64753 y Fj(X)16438 67582 y Fo(1)p Fp(\024)p Fq(`)f(x=m)p Fl(.)571 b(W)-108 b(e)412 b(write)g Ff(B)23478 7959 y Fo(5)p Fq(;)p Fo(2)25147 7760 y Fl(for)g(the)f(subset)g(of)h Ff(B)35930 7959 y Fo(5)36868 7760 y Fl(consisting)g(of)g(these)f(n)-36 b(um)g(b)36 b(ers.)800 9365 y(W)-108 b(e)437 b(write)h(also)g Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))376 b(=)f Fk(P)478 b Fl(+)298 b Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))374 b(=)h Fk(Q\016)50 b Fl(,)439 b(where)e(1)376 b Fg(\024)f Fk(\016)426 b(<)375 b(x)p Fl(\012)p Fk(=m)437 b Fl(is)h(some)g(p)36 b(ositiv)-36 b(e)438 b(in)-36 b(teger.)589 b(Since)800 10970 y Fk(P)787 b Fg(\024)606 b Fk(x=m)573 b Fl(is)g(uniquely)g (determined)f(mo)36 b(dulo)573 b Fk(Qt)p Fl(\()p Fk(Q)p Fl(\))605 b Fk(>)h(x=m)p Fl(,)i(it)573 b(follo)-36 b(ws)575 b(that)d Fk(P)754 b Fl(\(hence,)607 b Fk(n)p Fl(\))573 b(is)800 12575 y(uniquely)405 b(determined)e(b)-36 b(y)404 b Fk(Q)p Fl(.)569 b(W)-108 b(e)404 b(no)-36 b(w)405 b(\014x)f(b)36 b(oth)404 b Fk(m)g Fl(and)g Fk(\016)454 b Fl(and)404 b(observ)-36 b(e)405 b(that)f Fk(Q)369 b Fg(\024)g Fk(x)p Fl(\012)p Fk(=)p Fl(\()p Fk(m\016)50 b Fl(\).)569 b(Note)800 14180 y(also)435 b(that)11189 15785 y Fk(P)550 b Fl(=)368 b Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))296 b Fg(\000)f Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))368 b(=)h Fk(Q\016)345 b Fg(\000)295 b Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))369 b Fg(\021)g Fk(\016)345 b Fg(\000)295 b Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))1328 b(\(mo)36 b(d)442 b Fk(d)p Fl(\))p Fk(:)800 17870 y Fl(Since)503 b(also)i Fk(P)181 b(m)488 b Fg(\021)h Fl(1)591 b(\(mo)36 b(d)442 b Fk(d)p Fl(\),)522 b(w)-36 b(e)504 b(get)g(that)f Fk(d)h Fl(divides)g Fk(m)p Fl(\()p Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))341 b Fg(\000)j Fk(\016)50 b Fl(\))342 b(+)h(1.)789 b(This)504 b(last)h(n)-36 b(um)g(b)36 b(er)502 b(is)800 19476 y(not)397 b(zero)h(since)g Fk(m)369 b Fg(\025)g Fl(2)398 b(\(if)g(it)g(w)-36 b(ere)398 b(zero,)405 b(then)397 b Fk(m)p Fl(\()p Fk(\016)271 b Fg(\000)222 b Fk(\014)74 b Fl(\()p Fk(m)p Fl(\)\))368 b(=)h(1,)405 b(whic)-36 b(h)397 b(is)h(imp)36 b(ossible)399 b(for)f Fk(m)368 b Fg(\025)i Fl(2\).)800 21081 y(Since)433 b Fk(\016)419 b Fg(\025)369 b Fl(1,)434 b(the)f(size)h(of)h(this)e(n)-36 b(um)g(b)36 b(er)432 b(is)13305 23456 y Fg(j)p Fk(m)p Fl(\()p Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))294 b Fg(\000)i Fk(\016)50 b Fl(\))294 b(+)h(1)p Fg(j)1107 b Fk(<)g Fl(max)q Fg(f)p Fk(m\016)-22 b(;)221 b(mP)181 b Fl(\()p Fk(m)p Fl(\)\012\()p Fk(m)p Fl(\))p Fg(g)24758 25393 y Fk(<)1107 b Fl(max)q Fg(f)p Fk(xm)p Fl(\012)p Fk(;)221 b(m)34498 24844 y Fo(2)35024 25393 y Fl(\012)p Fg(g)24758 28119 y Fk(<)1107 b(xm)p Fl(\012)369 b Fk(<)31576 27221 y(x)32315 26738 y Fo(2)32841 27221 y Fl(\012)p 31576 27814 2205 54 v 32337 29030 a Fk(y)34282 28119 y(<)f(x)36401 27571 y Fo(2)800 31092 y Fl(for)434 b(large)h(v)-72 b(alues)434 b(of)g Fk(x)p Fl(.)578 b(Th)-36 b(us,)14854 34182 y(\012\()p Fg(j)p Fk(m)p Fl(\()p Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))294 b Fg(\000)h Fk(\016)50 b Fl(\))295 b(+)g(1)p Fg(j)p Fl(\))369 b Fk(<)29034 33283 y Fl(log)19 b(\()p Fk(x)31959 32801 y Fo(2)32484 33283 y Fl(\))p 29034 33877 3957 54 v 29736 35093 a(log)240 b(2)33492 34182 y Fk(<)369 b Fl(3)221 b(log)241 b Fk(x:)800 37228 y Fl(Since)447 b Fk(d)g Fl(is)h(a)g (divisor)g(of)g(the)f(\014xed)g(in)-36 b(teger)447 b Fk(m)p Fl(\()p Fk(\014)74 b Fl(\()p Fk(m)p Fl(\))304 b Fg(\000)g Fk(\016)50 b Fl(\))305 b(+)f(1)448 b(ha)-36 b(ving)447 b(\012\()p Fk(d)p Fl(\))393 b Fk(<)f Fl(\012,)451 b(it)d(follo)-36 b(ws)449 b(that)e Fk(d)800 38834 y Fl(can)434 b(b)36 b(e)433 b(c)-36 b(hosen)433 b(in)h(at)f(most)15411 37228 y SDict begin H.S end 15411 37228 a 15411 37228 a SDict begin 14.5 H.A end 15411 37228 a 15411 37228 a SDict begin [ /View [/XYZ H.V] /Dest (equation.8) cvn H.B /DEST pdfmark end 15411 37228 a 16362 41209 a Fl(\(3)221 b(log)241 b Fk(x)p Fl(\))20886 40660 y Fo(\012)21990 41209 y Fk(<)369 b Fl(exp)221 b(\(\(log)240 b(log)h Fk(x)295 b Fl(+)g(log)240 b(3\)\012\))13901 b(\(8\))800 43584 y(w)-36 b(a)g(ys)343 b(for)h(large)f(v)-72 b(alues)343 b(of)g Fk(x)p Fl(.)548 b(No)-36 b(w)343 b Fk(Q)370 b Fg(\024)f Fk(x)p Fl(\012)p Fk(=)p Fl(\()p Fk(m\016)50 b Fl(\))342 b(is)h(a)g(prime)f(with)h Fk(Q)369 b Fg(\021)g Fl(1)591 b(\(mo)36 b(d)442 b Fk(d)p Fl(\),)361 b(so)343 b(the)f(n)-36 b(um)g(b)36 b(er)800 45189 y(of)434 b(p)36 b(ossibilities)435 b(for)f Fk(Q)g Fl(\(hence,)f(for)h Fk(P)181 b Fl(\))433 b(is)24566 48208 y Fg(\024)26481 47309 y Fk(x)p Fl(\012)p 26101 47902 2440 54 v 26101 49119 a Fk(m\016)50 b(d)28673 48208 y(:)800 50996 y Fl(Keeping)548 b Fk(m)g Fl(and)g Fk(\016)598 b Fl(\014xed)548 b(and)g(summing)g(up)f(o)-36 b(v)g(er)549 b(all)g(the)f(p)36 b(ossible)548 b(v)-72 b(alues)549 b(of)g Fk(d)f Fl(\(the)g(n)-36 b(um)g(b)36 b(er)546 b(of)800 52601 y(whic)-36 b(h)510 b(is)h(indicated)f(b)-36 b(y)511 b(upp)36 b(er)509 b(b)36 b(ound)509 b(\()p 0 .5 0 TeXcolorrgb 21971 52601 a SDict begin H.S end 21971 52601 a 0 .5 0 TeXcolorrgb Fl(8)p 0 .5 0 TeXcolorrgb 22622 51745 a SDict begin H.R end 22622 51745 a 22622 52601 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.8) cvn H.B /ANN pdfmark end 22622 52601 a Black Fl(\))o(\))i(w)-36 b(e)510 b(conclude)h(that)f(once)g Fk(m)g Fl(and)g Fk(\016)561 b Fl(are)511 b(\014xed,)529 b(then)510 b Fk(Q)800 54206 y Fl(\(hence,)433 b Fk(P)181 b Fl(;)434 b(so)g(also)g Fk(n)p Fl(\))g(can)g(b)36 b(e)433 b(\014xed)g(in)h(at)g(most)18917 56415 y Fk(x)p Fl(\012)221 b(exp)h(\(\(log)240 b(log)h Fk(x)295 b Fl(+)g(log)240 b(3\)\012\))p 18917 57008 15767 54 v 24853 58225 a Fk(z)25516 57841 y Fo(1)p Fq(=)p Fo(3)26983 58225 y Fk(m\016)800 60102 y Fl(w)-36 b(a)g(ys.)579 b(Summing)433 b(up)g(o)-36 b(v)g(er)434 b(all)g(the)f(p)36 b(ossibilities)435 b(for)f Fk(\016)419 b(<)369 b(x)p Fl(\012)434 b(and)f Fk(m)368 b Fg(\024)i Fk(x=y)48 b Fl(,)434 b(w)-36 b(e)434 b(get)f(that)10701 63069 y SDict begin H.S end 10701 63069 a 10701 63069 a SDict begin 14.5 H.A end 10701 63069 a 10701 63069 a SDict begin [ /View [/XYZ H.V] /Dest (equation.9) cvn H.B /DEST pdfmark end 10701 63069 a Fl(#)p Ff(B)12959 63268 y Fo(5)p Fq(;)p Fo(2)15471 63069 y Fg(\024)18587 62171 y Fk(x)p 17892 62764 2131 54 v 17892 63980 a(z)18555 63597 y Fo(1)p Fq(=)p Fo(3)20376 63069 y Fl(exp)221 b(\(\(log)240 b(log)h Fk(x)295 b Fl(+)g(log)240 b(3\)\012\))35035 61807 y Fj(X)34464 64685 y Fq(m)p Fp(\024)p Fq(x=y)38123 62171 y Fl(1)p 37879 62764 1138 54 v 37879 63980 a Fk(m)39607 61807 y Fj(X)39371 64636 y Fq(\016)33 b Fp(\024)p Fq(x)p Fo(\012)42116 62171 y Fl(1)p 42116 62764 651 54 v 42128 63980 a Fk(\016)15323 66953 y Fg(\034)18587 66054 y Fk(x)p 17892 66647 2131 54 v 17892 67864 a(z)18555 67480 y Fo(1)p Fq(=)p Fo(3)20155 66953 y Fl(\(log)240 b Fk(x)p Fl(\))23807 66404 y Fo(2)24554 66953 y Fl(exp)221 b(\(\(log)240 b(log)h Fk(x)295 b Fl(+)g(log)240 b(3\)\012\))p Black 12718 w(\(9\))p Black Black 26475 70521 a(5)p Black eop end end %%Page: 6 6 TeXDict begin HPSdict begin 6 5 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.6) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 1328 x Fl(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(.)579 b(Comparing)434 b(estimates)g(\()p 0 .5 0 TeXcolorrgb 20419 -2672 a SDict begin H.S end 20419 -2672 a 0 .5 0 TeXcolorrgb Fl(7)p 0 .5 0 TeXcolorrgb 21069 -3528 a SDict begin H.R end 21069 -3528 a 21069 -2672 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.7) cvn H.B /ANN pdfmark end 21069 -2672 a Black Fl(\))g(and)f(\()p 0 .5 0 TeXcolorrgb 25044 -2672 a SDict begin H.S end 25044 -2672 a 0 .5 0 TeXcolorrgb Fl(9)p 0 .5 0 TeXcolorrgb 25694 -3528 a SDict begin H.R end 25694 -3528 a 25694 -2672 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.9) cvn H.B /ANN pdfmark end 25694 -2672 a Black Fl(\),)h(w)-36 b(e)433 b(conclude)h(that)f(for)h(large)g Fk(x)g Fl(w)-36 b(e)434 b(ha)-36 b(v)g(e)9073 262 y SDict begin H.S end 9073 262 a 9073 262 a SDict begin 14.5 H.A end 9073 262 a 9073 262 a SDict begin [ /View [/XYZ H.V] /Dest (equation.10) cvn H.B /DEST pdfmark end 9073 262 a Fl(#)p Ff(B)11331 461 y Fo(5)12964 262 y Fg(\024)1107 b Fl(#)p Ff(B)17362 461 y Fo(5)p Fq(;)p Fo(1)18915 262 y Fl(+)295 b(#)p Ff(B)22480 461 y Fo(5)p Fq(;)p Fo(2)12975 3002 y Fk(<)1117 b(x)221 b Fl(exp)18273 1129 y Fj(\022)19251 3002 y Fg(\000)20417 2104 y Fl(log)240 b Fk(z)p 20417 2697 2565 54 v 21374 3913 a Fl(3)23410 3002 y(+)295 b(\(log)240 b(log)g Fk(x)296 b Fl(+)e(log)241 b(3\)\012)296 b(+)e Fk(O)36 b Fl(\(log)241 b(log)f Fk(x)p Fl(\))43549 1129 y Fj(\023)p Black 50488 3002 a Fl(\(10\))p Black 800 6275 a(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(.)2751 7880 y Fe(The)569 b(set)f Ff(B)9465 8079 y Fo(6)9991 7880 y Fe(.)762 b Fl(Supp)36 b(ose)493 b(that)h Fk(n)474 b Fg(2)e Ff(B)22991 8079 y Fo(6)23517 7880 y Fl(.)762 b(Then)494 b(either)g Fk(t)p Fl(\()p Fk(Q)p Fl(\))473 b Fk(<)f(Q)37342 7398 y Fo(1)p Fq(=)p Fo(3)38809 7880 y Fl(,)510 b(or)495 b(\012\()p Fk(d)p Fl(\))473 b Fk(>)f Fl(\012.)762 b(Let)494 b Ff(B)51542 8079 y Fo(6)p Fq(;)p Fo(1)800 9485 y Fl(and)433 b Ff(B)4503 9684 y Fo(6)p Fq(;)p Fo(2)6195 9485 y Fl(b)36 b(e)433 b(the)g(subsets)g(of)h Ff(B)17362 9684 y Fo(6)18322 9485 y Fl(suc)-36 b(h)432 b(that)h(the)g(\014rst)g(and)g(second)h(inequalit)-36 b(y)434 b(holds,)g(resp)36 b(ectiv)-36 b(ely)-108 b(.)2751 11090 y(W)g(e)581 b(\014rst)g(deal)h(with)f Ff(B)15145 11289 y Fo(6)p Fq(;)p Fo(1)16403 11090 y Fl(.)1022 b(Let)581 b Fg(Q)g Fl(b)36 b(e)581 b(the)g(set)g(of)i(primes)e(suc)-36 b(h)580 b(that)h Fk(t)p Fl(\()p Fk(Q)p Fl(\))620 b Fk(<)g(Q)46231 10608 y Fo(1)p Fq(=)p Fo(3)47698 11090 y Fl(,)f(and)581 b(let)800 12695 y Fg(Q)p Fl(\()p Fk(t)p Fl(\))382 b(=)g Fg(Q)300 b(\\)h Fl([1)p Fk(;)221 b(t)p Fl(].)603 b(The)442 b(\014rst)f(few)h(elemen)-36 b(ts)441 b(of)i(the)e(set)g Fg(Q)g Fl(are)h Fg(f)p Fl(8191)p Fk(;)221 b Fl(43691)p Fk(;)g Fl(65537)p Fk(;)g(:)g(:)g(:)9 b Fg(g)p Fl(.)602 b(W)-108 b(e)442 b(\014rst)800 14301 y(sho)-36 b(w)480 b(that)f Fg(Q)h Fl(is)g(sparse.)716 b(Let)480 b Fk(t)f Fl(b)36 b(e)480 b(large)g(and)f(let)h Fk(k)493 b Fl(=)447 b(#)p Fg(Q)p Fl(\()p Fk(t)p Fl(\).)716 b(Let)479 b(8191)449 b(=)e Fk(q)42097 14500 y Fo(1)43070 14301 y Fk(<)g Fg(\001)221 b(\001)g(\001)448 b Fk(<)f(q)48562 14500 y Fq(k)49611 14301 y Fl(b)36 b(e)479 b(all)800 15906 y(the)433 b(n)-36 b(um)g(b)36 b(ers)432 b(in)i Fg(Q)p Fl(\()p Fk(t)p Fl(\).)577 b(Then)10906 20085 y(8191)13506 19537 y Fq(k)14445 20085 y Fk(<)16418 18425 y Fq(k)15826 18823 y Fj(Y)15913 21622 y Fq(i)p Fo(=1)17745 20085 y Fk(q)18322 20284 y Fq(i)19066 20085 y Fg(j)20353 18823 y Fj(Y)19804 21797 y Fq(j)51 b Fp(\024)p Fq(t)21308 21535 y Fd(1)p Fi(=)p Fd(3)22599 20085 y Fl(\(2)23755 19537 y Fq(j)24537 20085 y Fg(\000)295 b Fl(1\))369 b Fk(<)g Fl(2)29421 18713 y Fc(P)30415 19808 y Fi(j)39 b Fb(\024)p Fi(t)31751 19570 y Fd(1)p Fi(=)p Fd(3)33253 19377 y Fq(j)34109 20085 y Fk(<)368 b Fl(2)36139 19537 y Fq(t)36479 19224 y Fd(1)p Fi(=)p Fd(3)37771 19537 y Fo(\()p Fq(t)38477 19224 y Fd(1)p Fi(=)p Fd(3)39768 19537 y Fo(+1\))p Fq(=)p Fo(2)42332 20085 y Fk(;)800 24687 y Fl(whic)-36 b(h)403 b(leads)h(easily)h(to)e(the)g(conclusion)g (that)g(the)g(inequalit)-36 b(y)405 b Fk(k)414 b(<)368 b Fl(0)p Fk(:)p Fl(04)p Fk(t)37559 24205 y Fo(2)p Fq(=)p Fo(3)39430 24687 y Fl(holds)403 b(for)h(large)g(v)-72 b(alues)404 b(of)800 26292 y Fk(t)p Fl(.)578 b(By)434 b(partial)g(summation,)g(w)-36 b(e)434 b(conclude)f(that)g(uniformly)h (in)g Fk(s)368 b Fg(\024)h Fk(t)p Fl(,)434 b(w)-36 b(e)434 b(ha)-36 b(v)g(e)41615 24687 y SDict begin H.S end 41615 24687 a 41615 24687 a SDict begin 14.5 H.A end 41615 24687 a 41615 24687 a SDict begin [ /View [/XYZ H.V] /Dest (equation.11) cvn H.B /DEST pdfmark end 41615 24687 a 9960 28730 a Fj(X)9574 31536 y Fq(s)p Fp(\024)p Fq(q)32 b Fp(\024)p Fq(t)9995 32432 y(q)g Fp(2Q)12619 29093 y Fl(1)p 12619 29686 651 54 v 12632 30903 a Fk(q)13771 29991 y Fl(=)15151 28183 y Fj(Z)16480 28534 y Fq(t)15889 31191 y(s)17229 29093 y Fk(d)p Fl(#)p Fg(Q)p Fl(\()p Fk(u)p Fl(\))p 17229 29686 4597 54 v 19157 30903 a Fk(u)22327 29991 y Fl(=)23841 29093 y(#)p Fg(Q)p Fl(\()p Fk(u)p Fl(\))p 23841 29686 3921 54 v 25431 30903 a Fk(u)27894 28464 y Fj(\014)27894 29261 y(\014)27894 30058 y(\014)28337 28814 y Fq(u)p Fo(=)p Fq(t)28337 30910 y(u)p Fo(=)p Fq(s)30399 29991 y Fl(+)31706 28183 y Fj(Z)33034 28534 y Fq(t)32444 31191 y(s)33784 29093 y Fl(#)p Fg(Q)p Fl(\()p Fk(u)p Fl(\))p 33784 29686 V 35111 30903 a Fk(u)35851 30519 y Fo(2)37837 29991 y Fk(du)369 b Fg(\034)42167 29093 y Fl(1)p 41453 29686 2080 54 v 41453 30903 a Fk(s)42066 30519 y Fo(1)p Fq(=)p Fo(3)43665 29991 y Fk(:)6462 b Fl(\(11\))800 35173 y(Returning)312 b(to)g(our)g(problem,)337 b(let)312 b Fk(n)370 b Fg(2)e Ff(B)21152 35372 y Fo(6)p Fq(;)p Fo(1)22410 35173 y Fl(.)538 b(T)-108 b(o)313 b(coun)-36 b(t)312 b(suc)-36 b(h)311 b Fk(n)p Fl(,)337 b(write)313 b(again)h Fk(n)369 b Fl(=)f Fk(P)181 b(m)313 b Fl(and)e Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b(=)g Fk(Q\016)800 36778 y Fl(and)433 b(assume)h(that)f Fk(m)368 b Fg(\024)i Fk(x=y)481 b Fl(and)433 b Fk(Q)370 b Fg(2)e Fl([)p Fk(z)59 b(;)221 b(x)p Fl(\012])436 b(are)e(\014xed.)578 b(Then)433 b Fk(\016)483 b Fl(can)434 b(b)36 b(e)433 b(c)-36 b(hosen)433 b(in)h(at)g(most)25961 39457 y Fk(x)p Fl(\012)p 25716 40050 2168 54 v 25716 41267 a Fk(mQ)800 43960 y Fl(w)-36 b(a)g(ys.)597 b(Note)440 b(that)f Fk(Q)379 b Fg(2)f(Q)p Fl(.)596 b(Summing)439 b(up)f(the)h(ab)36 b(o)-36 b(v)g(e)440 b(b)36 b(ound)439 b(o)-36 b(v)g(er)440 b Fk(m)378 b Fg(\024)h Fk(x=y)488 b Fl(and)439 b Fk(Q)379 b Fg(2)g(Q)299 b(\\)g Fl([)p Fk(z)59 b(;)221 b(x)p Fl(\012],)800 45565 y(w)-36 b(e)434 b(get)g(that)17165 49017 y SDict begin H.S end 17165 49017 a 17165 49017 a SDict begin 14.5 H.A end 17165 49017 a 17165 49017 a SDict begin [ /View [/XYZ H.V] /Dest (equation.12) cvn H.B /DEST pdfmark end 17165 49017 a Fl(#)p Ff(B)19423 49216 y Fo(6)p Fq(;)p Fo(1)21788 49017 y Fg(\034)1107 b Fk(x)p Fl(\012)26694 47755 y Fj(X)26122 50633 y Fq(m)p Fp(\024)p Fq(x=y)29782 48119 y Fl(1)p 29538 48712 1138 54 v 29538 49928 a Fk(m)32015 47755 y Fj(X)31030 50574 y Fq(z)37 b Fp(\024)p Fq(Q)p Fp(\024)p Fq(x)p Fo(\012)31906 51471 y Fq(Q)p Fp(2Q)35462 48119 y Fl(1)p 35272 48712 1031 54 v 35272 49928 a Fk(Q)21788 54114 y Fg(\034)24356 53215 y Fk(x)p Fl(\(log)240 b Fk(x)p Fl(\)\012)p 24356 53808 5331 54 v 25956 55025 a Fk(z)26619 54641 y Fo(1)p Fq(=)p Fo(3)30188 54114 y Fl(=)33592 53215 y Fk(x)p 31702 53808 4520 54 v 31702 55025 a(z)32365 54641 y Fo(1)p Fq(=)p Fo(3+)p Fq(o)p Fo(\(1\))p Black 50488 54114 a Fl(\(12\))p Black 800 57460 a(as)567 b Fk(x)597 b Fg(!)f(1)p Fl(,)601 b(where)567 b(in)g(the)g(ab)36 b(o)-36 b(v)g(e)568 b(estimate)f(w)-36 b(e)567 b(used)g(the)f(upp)36 b(er)566 b(b)36 b(ound)566 b(\()p 0 .5 0 TeXcolorrgb 41188 57460 a SDict begin H.S end 41188 57460 a 0 .5 0 TeXcolorrgb Fl(11)p 0 .5 0 TeXcolorrgb 42488 56604 a SDict begin H.R end 42488 56604 a 42488 57460 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.11) cvn H.B /ANN pdfmark end 42488 57460 a Black Fl(\))h(with)g Fk(s)596 b Fl(=)g Fk(z)627 b Fl(and)800 59066 y Fk(t)369 b Fl(=)f Fk(x)p Fl(\012.)2751 60671 y(W)-108 b(e)645 b(no)-36 b(w)644 b(deal)h(with)g Ff(B)15427 60870 y Fo(6)p Fq(;)p Fo(2)16685 60671 y Fl(.)1211 b(Note)645 b(that)f(for)i(suc)-36 b(h)643 b(n)-36 b(um)g(b)36 b(ers,)697 b Fk(Q)439 b Fg(\000)g Fl(1)645 b(is)g(a)f(m)-36 b(ultiple)645 b(of)g Fk(d)p Fl(,)698 b(so)800 62276 y(\012\()p Fk(Q)217 b Fg(\000)g Fl(1\))369 b Fg(\025)g Fl(\012\()p Fk(d)p Fl(\))g Fk(>)g Fl(\012.)566 b(Fix)396 b Fk(m)e Fl(and)h Fk(Q)369 b(<)g(x)p Fl(\012.)566 b(Then)395 b Fk(\016)445 b Fl(\(hence,)402 b Fk(P)181 b Fl(;)409 b(so,)403 b Fk(n)p Fl(\))395 b(can)h(b)36 b(e)395 b(\014xed)g(in)g(at)g(most)800 62276 y SDict begin H.S end 800 62276 a 800 62276 a SDict begin 14.5 H.A end 800 62276 a 800 62276 a SDict begin [ /View [/XYZ H.V] /Dest (equation.13) cvn H.B /DEST pdfmark end 800 62276 a 23301 64899 a Fk(x)p Fl(\012)p 23301 65492 1679 54 v 23625 66709 a Fk(Q)25481 65798 y(<)27808 64899 y(x)p Fl(\012)p 26995 65492 3305 54 v 26995 66709 a Fk(Q)295 b Fg(\000)h Fl(1)50488 65798 y(\(13\))p Black 26475 70521 a(6)p Black eop end end %%Page: 7 7 TeXDict begin HPSdict begin 7 6 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.7) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 1328 x Fl(w)-36 b(a)g(ys.)655 b(It)458 b(follo)-36 b(ws)461 b(easily)f(b)-36 b(y)459 b(partial)g(summation)g (from)g(form)-36 b(ula)459 b(\()p 0 .5 0 TeXcolorrgb 35067 -2672 a SDict begin H.S end 35067 -2672 a 0 .5 0 TeXcolorrgb Fl(3)p 0 .5 0 TeXcolorrgb 35717 -3528 a SDict begin H.R end 35717 -3528 a 35717 -2672 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.3) cvn H.B /ANN pdfmark end 35717 -2672 a Black Fl(\))g(that)f(uniformly)h(in)g Fk(k)e Fg(\025)412 b Fl(1)459 b(and)800 -1067 y Fk(t)p Fl(,)434 b(w)-36 b(e)433 b(ha)-36 b(v)g(e)6978 -2672 y SDict begin H.S end 6978 -2672 a 6978 -2672 a SDict begin 14.5 H.A end 6978 -2672 a 6978 -2672 a SDict begin [ /View [/XYZ H.V] /Dest (equation.14) cvn H.B /DEST pdfmark end 6978 -2672 a 21548 -8 a Fj(X)21686 2798 y Fq(n)p Fp(\024)p Fq(t)20893 3731 y Fo(\012\()p Fq(n)p Fo(\))p Fp(\025)p Fq(k)24538 355 y Fl(1)p 24475 948 777 54 v 24475 2165 a Fk(n)25753 1254 y Fg(\034)27583 355 y Fk(k)45 b Fl(\(log)241 b Fk(t)p Fl(\))31688 -127 y Fo(2)p 27583 948 4630 54 v 29289 2165 a Fl(2)29939 1781 y Fq(k)32346 1254 y Fk(:)17781 b Fl(\(14\))800 5906 y(Summing)499 b(up)g(b)36 b(ounds)498 b(\()p 0 .5 0 TeXcolorrgb 13687 5906 a SDict begin H.S end 13687 5906 a 0 .5 0 TeXcolorrgb Fl(13)p 0 .5 0 TeXcolorrgb 14987 5050 a SDict begin H.R end 14987 5050 a 14987 5906 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.13) cvn H.B /ANN pdfmark end 14987 5906 a Black Fl(\))i(o)-36 b(v)g(er)500 b(all)g(primes)f Fk(Q)h Fl(with)g(\012\()p Fk(Q)340 b Fg(\000)g Fl(1\))482 b Fk(>)f Fl(\012)500 b(and)f(using)g(b)36 b(ound)499 b(\()p 0 .5 0 TeXcolorrgb 48941 5906 a SDict begin H.S end 48941 5906 a 0 .5 0 TeXcolorrgb Fl(14)p 0 .5 0 TeXcolorrgb 50241 5050 a SDict begin H.R end 50241 5050 a 50241 5906 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.14) cvn H.B /ANN pdfmark end 50241 5906 a Black Fl(\))g(for)800 7511 y Fk(t)369 b Fl(=)f Fk(x)p Fl(\012)434 b(and)f Fk(k)414 b Fl(=)369 b Fg(b)p Fl(\012)p Fg(c)p Fl(,)435 b(w)-36 b(e)434 b(get)g(that)19947 5906 y SDict begin H.S end 19947 5906 a 19947 5906 a SDict begin 14.5 H.A end 19947 5906 a 19947 5906 a SDict begin [ /View [/XYZ H.V] /Dest (equation.15) cvn H.B /DEST pdfmark end 19947 5906 a 13118 11221 a Fl(#)p Ff(B)15376 11420 y Fo(6)p Fq(;)p Fo(2)17003 11221 y Fg(\034)18833 10322 y Fk(x)p Fl(\(log)240 b Fk(x)p Fl(\))23224 9840 y Fo(2)23750 10322 y Fl(\012)24689 9840 y Fo(2)p 18833 10915 6383 54 v 21331 12132 a Fl(2)21981 11748 y Fo(\012)25717 11221 y Fl(=)369 b Fk(x)221 b Fl(exp\()p Fg(\000)p Fl(\(log)240 b(2)296 b(+)f Fk(o)p Fl(\(1\)\)\012\))10006 b(\(15\))800 14554 y(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(.)579 b(F)-108 b(rom)433 b(estimates)h(\()p 0 .5 0 TeXcolorrgb 17113 14554 a SDict begin H.S end 17113 14554 a 0 .5 0 TeXcolorrgb Fl(12)p 0 .5 0 TeXcolorrgb 18414 13698 a SDict begin H.R end 18414 13698 a 18414 14554 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.12) cvn H.B /ANN pdfmark end 18414 14554 a Black Fl(\))f(and)g(\()p 0 .5 0 TeXcolorrgb 22388 14554 a SDict begin H.S end 22388 14554 a 0 .5 0 TeXcolorrgb Fl(15)p 0 .5 0 TeXcolorrgb 23688 13698 a SDict begin H.R end 23688 13698 a 23688 14554 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.15) cvn H.B /ANN pdfmark end 23688 14554 a Black Fl(\),)h(w)-36 b(e)434 b(get)29072 12949 y SDict begin H.S end 29072 12949 a 29072 12949 a SDict begin 14.5 H.A end 29072 12949 a 29072 12949 a SDict begin [ /View [/XYZ H.V] /Dest (equation.16) cvn H.B /DEST pdfmark end 29072 12949 a 15390 17783 a Fl(#)p Ff(B)17648 17982 y Fo(6)18543 17783 y Fg(\024)21968 16884 y Fk(x)p 20078 17477 4520 54 v 20078 18694 a(z)20741 18310 y Fo(1)p Fq(=)p Fo(3+)p Fq(o)p Fo(\(1\))25025 17783 y Fl(+)31901 16884 y Fk(x)p 26465 17477 11613 54 v 26465 18694 a Fl(exp)221 b(\(\(log)240 b(2)296 b(+)f Fk(o)p Fl(\(1\)\)\012\))50488 17783 y(\(16\))800 21024 y(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(.)2751 22629 y(Comparing)465 b(b)36 b(ounds)462 b(\()p 0 .5 0 TeXcolorrgb 14561 22629 a SDict begin H.S end 14561 22629 a 0 .5 0 TeXcolorrgb Fl(1)p 0 .5 0 TeXcolorrgb 15211 21773 a SDict begin H.R end 15211 21773 a 15211 22629 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.1) cvn H.B /ANN pdfmark end 15211 22629 a Black Fl(\),)472 b(\()p 0 .5 0 TeXcolorrgb 17056 22629 a SDict begin H.S end 17056 22629 a 0 .5 0 TeXcolorrgb Fl(2)p 0 .5 0 TeXcolorrgb 17706 21773 a SDict begin H.R end 17706 21773 a 17706 22629 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.2) cvn H.B /ANN pdfmark end 17706 22629 a Black Fl(\),)g(\()p 0 .5 0 TeXcolorrgb 19551 22629 a SDict begin H.S end 19551 22629 a 0 .5 0 TeXcolorrgb Fl(4)p 0 .5 0 TeXcolorrgb 20201 21773 a SDict begin H.R end 20201 21773 a 20201 22629 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.4) cvn H.B /ANN pdfmark end 20201 22629 a Black Fl(\),)g(\()p 0 .5 0 TeXcolorrgb 22046 22629 a SDict begin H.S end 22046 22629 a 0 .5 0 TeXcolorrgb Fl(5)p 0 .5 0 TeXcolorrgb 22696 21773 a SDict begin H.R end 22696 21773 a 22696 22629 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.5) cvn H.B /ANN pdfmark end 22696 22629 a Black Fl(\),)f(\()p 0 .5 0 TeXcolorrgb 24540 22629 a SDict begin H.S end 24540 22629 a 0 .5 0 TeXcolorrgb Fl(10)p 0 .5 0 TeXcolorrgb 25841 21773 a SDict begin H.R end 25841 21773 a 25841 22629 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.10) cvn H.B /ANN pdfmark end 25841 22629 a Black Fl(\))464 b(and)f(\()p 0 .5 0 TeXcolorrgb 29876 22629 a SDict begin H.S end 29876 22629 a 0 .5 0 TeXcolorrgb Fl(16)p 0 .5 0 TeXcolorrgb 31177 21773 a SDict begin H.R end 31177 21773 a 31177 22629 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.16) cvn H.B /ANN pdfmark end 31177 22629 a Black Fl(\))o(,)472 b(w)-36 b(e)465 b(see)f(that)f(the)h(optimal)g(b)36 b(ounds)463 b(are)800 24234 y(obtained)433 b(when)g(the)g(parameters)h Fk(y)48 b(;)655 b(z)493 b Fl(and)433 b(\012)h(are)g(c)-36 b(hosen)433 b(suc)-36 b(h)432 b(that)11049 27739 y(\012)221 b(log)241 b(2)369 b(=)16644 26841 y(log)240 b Fk(z)p 16644 27434 2565 54 v 17601 28650 a Fl(3)19637 27739 y Fg(\000)295 b Fl(\(log)240 b(log)h Fk(x)295 b Fl(+)g(log)240 b(3\)\012)370 b(=)e Fk(v)269 b Fl(log)241 b Fk(v)416 b Fl(=)369 b Fk(u)221 b Fl(log)241 b Fk(u:)800 30999 y Fl(This)434 b(giv)-36 b(es)14541 33919 y(log)241 b Fk(y)1155 b Fl(=)1106 b(\()p Fk(c)21416 34118 y Fo(1)22237 33919 y Fl(+)295 b Fk(o)p Fl(\(1\)\)\(log)240 b Fk(x)p Fl(\))29989 33371 y Fo(2)p Fq(=)p Fo(3)31456 33919 y Fl(\(log)g(log)g Fk(x)p Fl(\))37009 33371 y Fo(2)p Fq(=)p Fo(3)38476 33919 y Fk(;)14560 35856 y Fl(log)g Fk(z)1167 b Fl(=)1106 b(\()p Fk(c)21416 36055 y Fo(2)22237 35856 y Fl(+)295 b Fk(o)p Fl(\(1\)\)\(log)240 b Fk(x)p Fl(\))29989 35308 y Fo(1)p Fq(=)p Fo(3)31456 35856 y Fl(\(log)g(log)g Fk(x)p Fl(\))37009 35308 y Fo(4)p Fq(=)p Fo(3)38476 35856 y Fk(;)16185 37793 y Fl(\012)1108 b(=)e(\()p Fk(c)21416 37992 y Fo(3)22237 37793 y Fl(+)295 b Fk(o)p Fl(\(1\)\)\(log)240 b Fk(x)p Fl(\))29989 37245 y Fo(1)p Fq(=)p Fo(3)31456 37793 y Fl(\(log)g(log)g Fk(x)p Fl(\))37009 37245 y Fo(1)p Fq(=)p Fo(3)800 40714 y Fl(as)488 b Fk(x)461 b Fg(!)g(1)p Fl(,)501 b(where)488 b Fk(c)12002 40913 y Fo(1)12988 40714 y Fl(=)460 b(\(log)241 b(2\))18024 40232 y Fp(\000)p Fo(1)p Fq(=)p Fo(3)20222 40714 y Fk(;)709 b(c)21852 40913 y Fo(2)22839 40714 y Fl(=)460 b(\(log)240 b(2\))27874 40232 y Fp(\000)p Fo(2)p Fq(=)p Fo(3)30073 40714 y Fk(;)709 b(c)31703 40913 y Fo(3)32689 40714 y Fl(=)461 b Fk(c)34722 40913 y Fo(2)35247 40714 y Fk(=)p Fl(3.)741 b(Note)488 b(that)f(this)g(agrees)h(with)800 42319 y(the)365 b(con)-36 b(v)g(en)g(tions)366 b(w)-36 b(e)366 b(made)g(at)g(the)f(b)36 b(eginning)366 b(on)f Fk(y)48 b(;)588 b(z)59 b(;)588 b Fl(\012)366 b(with)g Fk(\013)378 b Fl(=)368 b(2)p Fk(=)p Fl(3)p Fk(;)589 b(\014)443 b Fl(=)368 b Fk(\015)441 b Fl(=)369 b(1)p Fk(=)p Fl(3.)556 b(Therefore)800 43924 y(w)-36 b(e)434 b(ha)-36 b(v)g(e)434 b(just)f(sho)-36 b(wn)433 b(that)15050 42319 y SDict begin H.S end 15050 42319 a 15050 42319 a SDict begin 14.5 H.A end 15050 42319 a 15050 42319 a SDict begin [ /View [/XYZ H.V] /Dest (equation.17) cvn H.B /DEST pdfmark end 15050 42319 a 13266 46844 a Fl(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))369 b Fg(\024)g Fk(x)221 b Fl(exp)22215 45768 y Fj(\000)22824 46844 y Fg(\000)p Fl(\()p Fk(c)24923 47043 y Fo(4)25743 46844 y Fl(+)295 b Fk(o)p Fl(\(1\)\)\(log)240 b Fk(x)221 b Fl(log)241 b(log)g Fk(x)p Fl(\))38259 46296 y Fo(1)p Fq(=)p Fo(3)39725 45768 y Fj(\001)50488 46844 y Fl(\(17\))800 49881 y(as)434 b Fk(x)369 b Fg(!)g(1)p Fl(,)435 b(where)e Fk(c)11643 50080 y Fo(4)12538 49881 y Fl(=)368 b(\(log)240 b(2\))17481 49399 y Fo(1)p Fq(=)p Fo(3)18948 49881 y Fk(=)p Fl(3.)579 b(This)434 b(\014nishes)f(the)g(pro)36 b(of)434 b(of)h(Theorem)p 0 .5 0 TeXcolorrgb 41334 49881 a SDict begin H.S end 41334 49881 a 0 .5 0 TeXcolorrgb Fl(1)p 0 .5 0 TeXcolorrgb 41985 49025 a SDict begin H.R end 41985 49025 a 41985 49881 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (prop.1) cvn H.B /ANN pdfmark end 41985 49881 a Black Fl(.)800 52147 y Fe(Remark.)1030 b Fl(Notice)585 b(that)f(as)g(a)h(b)-36 b(ypro)36 b(duct)583 b(of)i(our)f(e\013ort)g(w) -36 b(e)584 b(conclude)g(immediately)-108 b(,)622 b(b)-36 b(y)585 b(partial)800 53752 y(summation,)434 b(that)23489 54614 y Fj(X)23443 57442 y Fq(n)p Fp(2)p Fa(B)25871 54977 y Fl(1)p 25808 55570 777 54 v 25808 56787 a Fk(n)27087 55876 y(<)368 b Fg(1)p Fk(:)800 59630 y SDict begin H.S end 800 59630 a 800 59630 a SDict begin 14.5 H.A end 800 59630 a 800 59630 a SDict begin [ /View [/XYZ H.V] /Dest (section.3) cvn H.B /DEST pdfmark end 800 59630 a 1439 x Fm(3)2152 b(Pro)60 b(of)716 b(of)h(Theorem)p 0 .5 0 TeXcolorrgb 21536 61069 a SDict begin H.S end 21536 61069 a 0 .5 0 TeXcolorrgb Fm(2)p 0 .5 0 TeXcolorrgb 22612 59837 a SDict begin H.R end 22612 59837 a 22612 61069 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (prop.2) cvn H.B /ANN pdfmark end 22612 61069 a Black 800 63990 a Fl(W)-108 b(e)371 b(let)g Fk(p)g Fl(b)36 b(e)371 b(a)g(large)h(prime)f(and)f(put)g Fk(M)508 b Fl(=)369 b(2)23871 63508 y Fq(p)24568 63990 y Fg(\000)167 b Fl(1.)558 b(Let)371 b Fk(k)416 b Fl(b)36 b(e)371 b(a)g(p)36 b(ositiv)-36 b(e)372 b(in)-36 b(teger)371 b(suc)-36 b(h)370 b(that)h Fk(k)414 b Fl(=)368 b Fk(o)p Fl(\()p Fk(p)p Fl(\))800 65595 y(holds)594 b(as)g Fk(p)641 b Fg(!)i(1)p Fl(.)1059 b(Cho)36 b(ose)595 b(p)36 b(ositiv)-36 b(e)595 b(in)-36 b(tegers)593 b Fk(a)642 b Fg(\025)g Fl(3)594 b(and)f Fk(b)h Fl(ev)-36 b(en)594 b(suc)-36 b(h)593 b(that)g Fk(a)405 b Fl(+)e Fk(b)642 b Fl(=)g Fk(k)d Fl(and)800 67200 y Fk(a)298 b Fg(\000)h Fk(b)377 b Fl(=)g(1.)593 b(Clearly)-108 b(,)441 b Fk(a)376 b Fl(=)h(\()p Fk(k)343 b Fl(+)298 b(1\))p Fk(=)p Fl(2)440 b(and)d Fk(b)377 b Fl(=)g(\()p Fk(k)343 b Fg(\000)299 b Fl(1\))p Fk(=)p Fl(2,)441 b(and)c(in)i(order)f(for)g Fk(a)g Fl(and)g Fk(b)h Fl(to)f(b)36 b(e)438 b(in)-36 b(tegers)p Black 26475 70521 a(7)p Black eop end end %%Page: 8 8 TeXDict begin HPSdict begin 8 7 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.8) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 1328 x Fl(with)498 b Fk(b)g Fl(ev)-36 b(en)498 b(w)-36 b(e)499 b(m)-36 b(ust)497 b(ha)-36 b(v)g(e)498 b Fk(k)524 b Fg(\021)479 b Fl(1)591 b(\(mo)36 b(d)442 b(4\).)772 b(F)-108 b(rom)498 b(no)-36 b(w)498 b(on,)514 b(w)-36 b(e)499 b(w)-36 b(ork)499 b(under)d(this)i(assumption.)800 -1067 y(Let)442 b Fg(I)482 b Fl(=)383 b Fg(b)p Fk(M)66 b(=)p Fl(\(2)p Fk(p)10112 -1549 y Fo(2)10640 -1067 y Fl(\))p Fk(;)221 b(M)66 b(=p)14355 -1549 y Fo(2)14882 -1067 y Fg(c)p Fl(.)605 b(W)-108 b(e)442 b(c)-36 b(ho)36 b(ose)443 b Fk(a)301 b Fg(\000)g Fl(3)442 b(distinct)g(primes)g(in)g Fg(I)541 b Fl(whic)-36 b(h)442 b(are)g(1)h(mo)36 b(dulo)442 b Fk(p)h Fl(and)800 539 y Fk(b)513 b Fl(distinct)g(primes)g(in)g Fg(I)612 b Fl(whic)-36 b(h)513 b(are)g Fg(\000)p Fl(1)h(mo)36 b(dulo)513 b Fk(p)p Fl(.)817 b(By)514 b(the)f(Siegel-W)-108 b(al\014sz)513 b(Theorem)h(\(note)e(that)800 2144 y(that)475 b(the)g(inequalit)-36 b(y)477 b Fk(p)440 b(<)g Fl(2)221 b(log)19 b(\()p Fk(M)66 b(=)p Fl(\(2)p Fk(p)21403 1662 y Fo(2)21930 2144 y Fl(\)\))475 b(holds)g(for)h(large)h(enough)e(v)-72 b(alues)476 b(of)g Fk(p)f Fl(so)h(w)-36 b(e)476 b(ma)-36 b(y)476 b(apply)800 3749 y(the)503 b(Siegel-W)-108 b(al\014sz)504 b(Theorem)f(to)h(estimate)g(the)f(n)-36 b(um)g(b)36 b(er)502 b(of)i(primes)f(congruen)-36 b(t)502 b(to)i(either)f(1)h(or)g Fg(\000)p Fl(1)800 5354 y(mo)36 b(dulo)434 b Fk(p)f Fl(in)h Fg(I)98 b Fl(\),)434 b(it)f(follo)-36 b(ws)436 b(that)d(the)g (inequalit)-36 b(y)7453 8859 y Fk(U)8336 9058 y Fq(\021)9265 8859 y Fl(=)369 b Fk(\031)48 b Fl(\()p Fk(M)66 b(=p)14565 8311 y Fo(2)15091 8859 y Fl(;)221 b Fk(p;)g(\021)48 b Fl(\))295 b Fg(\000)h Fk(\031)48 b Fl(\()p Fk(M)66 b(=)p Fl(\(2)p Fk(p)24803 8311 y Fo(2)25329 8859 y Fl(\);)221 b Fk(p;)g(\021)48 b Fl(\))369 b Fg(\025)32728 7961 y Fk(M)p 30752 8554 5349 54 v 30752 9771 a Fl(3)p Fk(p)32055 9387 y Fo(3)32802 9771 y Fl(log)241 b Fk(M)38835 8859 y Fl(for)434 b Fk(\021)416 b Fg(2)369 b(f\006)p Fl(1)p Fg(g)800 12392 y Fl(holds)319 b(for)h(large)g(v)-72 b(alues)320 b(of)g Fk(p)p Fl(.)540 b(Recall)321 b(that)e Fk(\031)48 b Fl(\()p Fk(x)p Fl(;)221 b Fk(v)48 b(;)221 b(u)p Fl(\))320 b(means)f(the)g(n)-36 b(um)g(b)36 b(er)317 b(of)k(primes)e Fk(p)368 b Fg(\024)i Fk(x)319 b Fl(congruen)-36 b(t)800 13997 y(to)434 b Fk(u)g Fl(mo)36 b(dulo)433 b Fk(v)48 b Fl(.)578 b(The)434 b(n)-36 b(um)g(b)36 b(er)432 b(of)i(c)-36 b(hoices)434 b(of)g(pairs)g(of)g(primes)f(as)h(ab)36 b(o)-36 b(v)g(e)435 b(is)13906 17813 y SDict begin H.S end 13906 17813 a 13906 17813 a SDict begin 14.5 H.A end 13906 17813 a 13906 17813 a SDict begin [ /View [/XYZ H.V] /Dest (equation.18) cvn H.B /DEST pdfmark end 13906 17813 a 1265 w Fl(=)17448 15940 y Fj(\022)19199 16915 y Fk(U)20082 17114 y Fo(1)18426 18725 y Fk(a)295 b Fg(\000)g Fl(3)21382 15940 y Fj(\023\022)23338 16915 y Fk(U)24221 17114 y Fp(\000)p Fo(1)24132 18725 y Fk(b)25479 15940 y Fj(\023)26826 17813 y Fg(\025)28228 15940 y Fj(\022)30112 16915 y Fk(U)30995 17114 y Fo(1)p 29339 17508 2957 54 v 29339 18725 a Fk(a)g Fg(\000)g Fl(3)32428 15940 y Fj(\023)33406 16238 y Fq(a)p Fp(\000)p Fo(3)35385 15940 y Fj(\022)36495 16915 y Fk(U)37378 17114 y Fo(1)p 36495 17508 1410 54 v 36923 18725 a Fk(b)38037 15940 y Fj(\023)39015 16238 y Fq(b)15160 21734 y Fg(\025)17448 19861 y Fj(\022)18559 20835 y Fk(U)19442 21034 y Fo(1)p 18559 21428 V 18922 22645 a Fk(a)20101 19861 y Fj(\023)21078 20158 y Fq(a)p Fp(\000)p Fo(3)23057 19861 y Fj(\022)24168 20835 y Fk(U)25051 21034 y Fp(\000)p Fo(1)p 24168 21428 2142 54 v 24962 22645 a Fk(b)26442 19861 y Fj(\023)27420 20158 y Fq(b)28099 19861 y Fj(\022)29077 21734 y Fl(1)g(+)g Fk(O)32580 19861 y Fj(\022)33691 20835 y Fk(k)45 b(p)35065 20353 y Fo(3)p 33691 21428 1900 54 v 33942 22645 a Fk(M)35724 19861 y Fj(\023)o(\023)37679 20133 y Fq(k)15013 25434 y Fg(\035)20445 24536 y Fk(M)21842 24054 y Fq(k)24 b Fp(\000)p Fo(3)p 17581 25129 8897 54 v 17581 26346 a Fl(\(3\(log)240 b(2\))p Fk(k)45 b(p)23674 25962 y Fo(4)24200 26346 y Fl(\))24706 25962 y Fq(k)24 b Fp(\000)p Fo(3)26979 25434 y Fg(\035)28907 24536 y Fk(M)30304 24054 y Fq(k)g Fp(\000)p Fo(3)p 28809 25129 3365 54 v 28809 26346 a Fk(p)29462 25962 y Fo(5)p Fq(k)g Fp(\000)p Fo(15)p Black 50488 25434 a Fl(\(18\))p Black 800 29041 a(since)585 b(3\(log)240 b(2\))p Fk(k)672 b(<)626 b(p)584 b Fl(for)h(large)h Fk(p)p Fl(.)1031 b(Here,)623 b(w)-36 b(e)585 b(also)h(used)e(the)g (fact)h(that)f(log)241 b Fk(M)765 b(<)626 b(p)p Fl(\(log)240 b(2\).)1031 b(Let)800 30646 y Fk(p)1453 30845 y Fo(1)2348 30646 y Fk(<)368 b Fg(\001)221 b(\001)g(\001)370 b Fk(<)f(p)7681 30845 y Fq(a)p Fp(\000)p Fo(3)9871 30646 y Fl(and)433 b Fk(q)12977 30845 y Fo(1)13872 30646 y Fk(<)369 b Fg(\001)221 b(\001)g(\001)369 b Fk(<)g(q)19129 30845 y Fq(b)20020 30646 y Fl(b)36 b(e)433 b(suc)-36 b(h)433 b(primes.)578 b(Put)8377 34126 y Fk(N)507 b Fl(=)369 b Fk(p)11960 34325 y Fo(1)12780 34126 y Fl(+)295 b Fg(\001)221 b(\001)g(\001)296 b Fl(+)f Fk(p)17892 34325 y Fq(a)p Fp(\000)p Fo(3)19944 34126 y Fl(+)g Fk(q)21828 34325 y Fo(1)22649 34126 y Fl(+)g Fg(\001)221 b(\001)g(\001)296 b Fl(+)e Fk(q)27684 34325 y Fq(b)28511 34126 y Fk(<)369 b Fl(\()p Fk(a)294 b Fg(\000)i Fl(3)f(+)g Fk(b)p Fl(\))36148 33227 y Fk(M)p 36148 33820 1398 54 v 36257 35037 a(p)36910 34653 y Fo(2)38047 34126 y Fk(<)39560 33227 y(k)45 b(M)p 39560 33820 2119 54 v 40030 35037 a(p)40683 34653 y Fo(2)42180 34126 y Fk(<)43693 33227 y(M)p 43693 33820 1398 54 v 44066 35037 a(p)800 37585 y Fl(for)510 b(large)f(v)-72 b(alues)510 b(of)g Fk(p)p Fl(.)804 b(Note)509 b(also)h(that)e(since)i Fk(a)346 b Fl(+)g Fk(b)497 b Fl(=)g Fk(k)392 b Fg(\000)346 b Fl(3)510 b(is)f(ev)-36 b(en)509 b(and)f(all)i(the)f(ab)36 b(o)-36 b(v)g(e)509 b(primes)800 39190 y(are)404 b(o)36 b(dd)404 b(\(b)36 b(ecause)404 b Fk(M)66 b(=)p Fl(\(2)p Fk(p)14546 38708 y Fo(2)15073 39190 y Fl(\))369 b Fk(>)g Fl(2)404 b(for)h(large)g(v)-72 b(alues)405 b(of)g Fk(p)p Fl(\),)410 b(it)404 b(follo)-36 b(ws)406 b(that)e Fk(N)542 b Fl(is)405 b(ev)-36 b(en.)569 b(F)-108 b(urthermore,)800 40795 y Fk(N)577 b Fg(\021)438 b Fk(a)323 b Fg(\000)g Fl(3)g Fg(\000)g Fk(b)591 b Fl(\(mo)36 b(d)442 b Fk(p)p Fl(\))c Fg(\021)h(\000)p Fl(2)591 b(\(mo)36 b(d)442 b Fk(p)p Fl(\).)701 b(Th)-36 b(us,)484 b Fk(M)462 b Fg(\000)323 b Fk(N)577 b(>)438 b(M)462 b Fg(\000)323 b Fk(M)66 b(=p)475 b Fl(is)g(a)f(large)i(o)36 b(dd)474 b(n)-36 b(um)g(b)36 b(er)800 42400 y(whic)-36 b(h)433 b(is)h(congruen)-36 b(t)433 b(to)14809 45262 y(2)15459 44713 y Fq(p)16283 45262 y Fg(\000)296 b Fl(1)f Fg(\000)h Fk(N)507 b Fg(\021)369 b Fl(2)296 b Fg(\000)f Fl(1)g Fg(\000)h Fl(\()p Fg(\000)p Fl(2\))369 b Fg(\021)g Fl(3)1329 b(\(mo)36 b(d)442 b Fk(p)p Fl(\))p Fk(:)800 48123 y Fl(By)427 b(a)g(Theorem)g(of)h(Ay)-36 b(oub)426 b([)p 0 .5 0 TeXcolorrgb 15379 48123 a SDict begin H.S end 15379 48123 a 0 .5 0 TeXcolorrgb Fl(1)p 0 .5 0 TeXcolorrgb 16030 47267 a SDict begin H.R end 16030 47267 a 16030 48123 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Ay) cvn H.B /ANN pdfmark end 16030 48123 a Black Fl(])h(\(see)f(also)i([)p 0 .5 0 TeXcolorrgb 22382 48123 a SDict begin H.S end 22382 48123 a 0 .5 0 TeXcolorrgb Fl(4)p 0 .5 0 TeXcolorrgb 23033 47267 a SDict begin H.R end 23033 47267 a 23033 48123 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Ba) cvn H.B /ANN pdfmark end 23033 48123 a Black Fl(]\),)g(it)f(follo)-36 b(ws)429 b(that)d(for)h(large)h Fk(p)e Fl(the)g(n)-36 b(um)g(b)36 b(er)426 b Fk(M)420 b Fg(\000)281 b Fk(N)565 b Fl(can)800 49728 y(b)36 b(e)433 b(written)h(as)20374 51334 y Fk(M)g Fg(\000)296 b Fk(N)507 b Fl(=)369 b Fk(r)26911 51533 y Fo(1)27732 51334 y Fl(+)295 b Fk(r)29625 51533 y Fo(2)30446 51334 y Fl(+)g Fk(r)32339 51533 y Fo(3)32865 51334 y Fk(;)800 53627 y Fl(where)457 b Fk(r)5167 53826 y Fo(1)6103 53627 y Fk(<)410 b(r)8111 53826 y Fo(2)9046 53627 y Fk(<)g(r)11054 53826 y Fo(3)12037 53627 y Fl(are)458 b(distinct)f(primes)g(all)i(congruen)-36 b(t)456 b(to)i(1)g(mo)36 b(dulo)457 b Fk(p)p Fl(.)650 b(Moreo)-36 b(v)g(er,)465 b(the)457 b(n)-36 b(um)g(b)36 b(er)800 55232 y(of)434 b(suc)-36 b(h)433 b(represen)-36 b(tations)433 b(is)15534 53627 y SDict begin H.S end 15534 53627 a 15534 53627 a SDict begin 14.5 H.A end 15534 53627 a 15534 53627 a SDict begin [ /View [/XYZ H.V] /Dest (equation.19) cvn H.B /DEST pdfmark end 15534 53627 a 16583 58809 a Fg(\030)21659 57911 y Fk(pC)23243 58110 y Fq(M)94 b Fp(\000)p Fq(N)25869 57911 y Fk(M)27266 57429 y Fo(2)p 18118 58504 13215 54 v 18118 59720 a Fl(6\(\()p Fk(p)295 b Fg(\000)h Fl(1\))23213 59337 y Fo(3)24034 59720 y Fl(+)f(1\)\(log)240 b Fk(M)139 b Fl(\))30807 59337 y Fo(3)31466 58809 y Fl(\(1)295 b(+)g Fk(o)p Fl(\(1\)\))13471 b(\(19\))800 62342 y(as)434 b Fk(p)369 b Fg(!)g(1)p Fl(,)434 b(where)11099 65894 y Fk(C)12030 66093 y Fq(M)94 b Fp(\000)p Fq(N)15025 65894 y Fl(=)17165 64632 y Fj(Y)16405 67510 y Fq(`)p Fp(j)p Fq(M)g Fp(\000)p Fq(N)19843 64021 y Fj(\022)20821 65894 y Fl(1)296 b Fg(\000)26260 64995 y Fk(`)p 23228 65588 6610 54 v 23228 66805 a Fl(\()p Fk(`)f Fg(\000)g Fl(1\))27059 66421 y Fo(3)27880 66805 y Fl(+)g(1)29970 64021 y Fj(\023)31169 64632 y(Y)31225 67461 y Fq(`>)p Fo(2)33088 64021 y Fj(\022)34066 65894 y Fl(1)g(+)38304 64995 y(1)p 36451 65588 4358 54 v 36451 66805 a(\()p Fk(`)g Fg(\000)g Fl(1\))40282 66421 y Fo(3)40941 64021 y Fj(\023)42140 65894 y Fk(:)p Black 26475 70521 a Fl(8)p Black eop end end %%Page: 9 9 TeXDict begin HPSdict begin 9 8 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.9) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 1328 x Fl(Observ)-36 b(e)627 b(that)g Fk(C)9930 -2473 y Fq(M)94 b Fp(\000)p Fq(N)13255 -2672 y Fg(\035)699 b Fl(1.)1161 b(In)627 b(what)g(follo)-36 b(ws,)679 b(w)-36 b(e)627 b(will)i(see)f(that)f(at)g(least)h(half)g(of) g(the)f(ab)36 b(o)-36 b(v)g(e)800 -1067 y(represen)g(tations)405 b(will)h(ha)-36 b(v)g(e)406 b Fk(r)15768 -868 y Fo(1)16663 -1067 y Fk(>)369 b(M)66 b(=p)20671 -1549 y Fo(2)21197 -1067 y Fl(.)569 b(Indeed,)411 b(assume)405 b(that)h(this)f(is)h(not)f (so.)569 b(Then)405 b Fk(r)46069 -868 y Fo(1)46964 -1067 y Fg(\024)369 b Fk(M)66 b(=p)50993 -1549 y Fo(2)51926 -1067 y Fl(is)800 539 y(a)411 b(prime)e(congruen)-36 b(t)410 b(to)g(1)g(mo)36 b(dulo)411 b Fk(p)e Fl(and)h Fk(r)22951 738 y Fo(2)23846 539 y Fg(\024)369 b Fk(M)549 b Fl(is)411 b(a)f(prime)g(congruen)-36 b(t)409 b(to)i(1)f(mo)36 b(dulo)410 b Fk(p)p Fl(,)415 b(and)410 b(once)800 2144 y Fk(r)1386 2343 y Fo(1)2338 2144 y Fl(and)426 b Fk(r)5446 2343 y Fo(2)6398 2144 y Fl(are)h(c)-36 b(hosen)426 b(then)f Fk(r)16255 2343 y Fo(3)17207 2144 y Fl(is)i(\014xed)f(b)-36 b(y)426 b(the)g(equation)g Fk(r)31565 2343 y Fo(3)32460 2144 y Fl(=)369 b Fk(M)419 b Fg(\000)281 b Fk(N)418 b Fg(\000)281 b Fk(r)40192 2343 y Fo(1)40998 2144 y Fg(\000)f Fk(r)42897 2343 y Fo(2)43423 2144 y Fl(.)576 b(The)427 b(n)-36 b(um)g(b)36 b(er)424 b(of)800 3749 y(suc)-36 b(h)433 b(pairs)g(\()p Fk(r)8012 3948 y Fo(1)8538 3749 y Fk(;)221 b(r)9706 3948 y Fo(2)10233 3749 y Fl(\))433 b(is)11211 7471 y Fg(\024)370 b Fk(\031)48 b Fl(\()p Fk(M)66 b(=p)16533 6923 y Fo(2)17059 7471 y Fl(;)221 b Fk(p;)g Fl(1\))p Fk(\031)48 b Fl(\()p Fk(M)139 b Fl(;)221 b Fk(p;)g Fl(1\))371 b Fg(\034)29941 6573 y Fk(M)31338 6091 y Fo(2)p 27895 7166 6015 54 v 27895 8382 a Fk(p)28548 7999 y Fo(4)29073 8382 y Fl(\(log)241 b Fk(M)139 b Fl(\))33384 7999 y Fo(2)34411 7471 y Fg(\034)38287 6573 y Fk(M)39684 6091 y Fo(2)p 36241 7166 V 36241 8382 a Fk(p)36894 7999 y Fo(3)37420 8382 y Fl(\(log)240 b Fk(M)139 b Fl(\))41730 7999 y Fo(3)800 11076 y Fl(and)450 b(the)f(ab)36 b(o)-36 b(v)g(e)451 b(upp)36 b(er)449 b(b)36 b(ound)449 b(is)h(of)h(a)f (smaller)h(order)f(of)h(magnitude)e(then)h(the)f(function)h(app)36 b(earing)800 12681 y(at)434 b(\()p 0 .5 0 TeXcolorrgb 2896 12681 a SDict begin H.S end 2896 12681 a 0 .5 0 TeXcolorrgb Fl(19)p 0 .5 0 TeXcolorrgb 4196 11825 a SDict begin H.R end 4196 11825 a 4196 12681 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.19) cvn H.B /ANN pdfmark end 4196 12681 a Black Fl(\).)578 b(Th)-36 b(us,)434 b(for)g(large)g Fk(p)p Fl(,)g(there)f(are)21404 11076 y SDict begin H.S end 21404 11076 a 21404 11076 a SDict begin 14.5 H.A end 21404 11076 a 21404 11076 a SDict begin [ /View [/XYZ H.V] /Dest (equation.20) cvn H.B /DEST pdfmark end 21404 11076 a 20684 16404 a Fg(\035)24560 15505 y Fk(M)25957 15023 y Fo(2)p 22514 16098 6015 54 v 22514 17315 a Fk(p)23167 16931 y Fo(2)23693 17315 y Fl(\(log)240 b Fk(M)139 b Fl(\))28003 16931 y Fo(3)29030 16404 y Fg(\035)30861 15505 y Fk(M)32258 15023 y Fo(2)p 30861 16098 1923 54 v 31233 17315 a Fk(p)31886 16931 y Fo(5)50488 16404 y Fl(\(20\))800 20139 y(suc)-36 b(h)523 b(represen)-36 b(tations)523 b(where)h Fk(r)17359 20338 y Fo(1)18408 20139 y Fk(>)f(M)66 b(=p)22570 19657 y Fo(2)23097 20139 y Fl(.)849 b(F)-108 b(rom)524 b(no)-36 b(w)524 b(on)g(w)-36 b(e)524 b(w)-36 b(ork)525 b(with)f(suc)-36 b(h)524 b(represen)-36 b(tations.)800 21744 y(No)g(w)530 b(observ)-36 b(e)529 b(that)g Fg(f)p Fk(p)12816 21943 y Fo(1)13342 21744 y Fk(;)221 b(:)g(:)g(:)j(;)d(p)16908 21943 y Fq(a)p Fp(\000)p Fo(3)18666 21744 y Fk(;)g(q)19825 21943 y Fo(1)20351 21744 y Fk(;)g(:)g(:)g(:)i(;)e(q)23840 21943 y Fq(b)24299 21744 y Fk(;)g(r)25467 21943 y Fo(1)25993 21744 y Fk(;)g(r)27161 21943 y Fo(2)27688 21744 y Fk(;)g(r)28856 21943 y Fo(3)29383 21744 y Fg(g)529 b Fl(are)g(distinct)g(primes)g(b)36 b(ecause)529 b Fk(r)47427 21943 y Fo(1)48485 21744 y Fk(>)j(p)50682 21943 y Fq(a)p Fp(\000)p Fo(3)52439 21744 y Fl(.)800 23349 y(Let)433 b Fk(n)h Fl(b)36 b(e)433 b(the)h(pro)36 b(duct)432 b(of)i(the)f(ab)36 b(o)-36 b(v)g(e)435 b Fk(a)295 b Fl(+)f Fk(b)369 b Fl(=)g Fk(k)479 b Fl(primes.)578 b(Then)13968 27454 y Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b(=)18422 25794 y Fq(a)p Fp(\000)p Fo(3)18313 26193 y Fj(X)18511 28992 y Fq(i)p Fo(=1)20453 27454 y Fk(p)21106 27653 y Fq(i)21777 27454 y Fl(+)23842 25794 y Fq(b)23084 26193 y Fj(X)23226 28992 y Fq(j)51 b Fo(=1)25224 27454 y Fk(q)25801 27653 y Fq(j)26583 27454 y Fl(+)295 b Fk(r)28476 27653 y Fo(1)29297 27454 y Fl(+)g Fk(r)31190 27653 y Fo(2)32011 27454 y Fl(+)g Fk(r)33904 27653 y Fo(3)34799 27454 y Fl(=)368 b(2)36829 26906 y Fq(p)37654 27454 y Fg(\000)295 b Fl(1)800 31833 y(and)413 b Fk(n)369 b Fg(\021)g Fl(1)254 b Fg(\001)g Fl(\()p Fg(\000)p Fl(1\))10078 31351 y Fq(b)10905 31833 y Fg(\021)369 b Fl(1)590 b(\(mo)36 b(d)443 b Fk(p)p Fl(\),)417 b(therefore)c Fk(p)369 b Fg(j)g Fk(n)254 b Fg(\000)g Fl(1,)417 b(so)d Fk(\014)74 b Fl(\()p Fk(n)p Fl(\))369 b Fg(j)g Fl(2)35796 31351 y Fq(p)36579 31833 y Fg(\000)253 b Fl(1)370 b Fg(j)f Fl(2)40273 31351 y Fq(n)p Fp(\000)p Fo(1)42355 31833 y Fg(\000)254 b Fl(1.)572 b(Th)-36 b(us,)417 b Fk(n)369 b Fg(2)g Ff(B)p Fl(.)800 33438 y(The)434 b(size)g(of)g Fk(n)g Fl(is)22652 35043 y Fk(n)370 b(<)e(M)26575 34495 y Fq(k)27513 35043 y Fk(<)h Fl(2)29544 34495 y Fq(pk)30587 35043 y Fk(:)800 37368 y Fl(W)-108 b(e)602 b(write)h Fk(x)656 b Fl(=)g(2)10414 36886 y Fq(pk)11457 37368 y Fl(.)1084 b(Th)-36 b(us,)644 b Fk(pk)701 b Fl(=)656 b(\(log)240 b Fk(x)p Fl(\))p Fk(=)p Fl(\(log)h(2\).)1084 b(By)603 b(unique)f(factorization,)646 b(it)602 b(follo)-36 b(ws)604 b(that)800 38973 y(p)36 b(ositiv)-36 b(e)435 b(in)-36 b(tegers)433 b Fk(n)h Fl(arising)g(from)g(distinct)f(sets)h(of)g (primes)17404 41906 y Fg(f)p Fk(p)18721 42105 y Fo(1)19247 41906 y Fk(;)221 b(:)g(:)g(:)i(;)e(p)22812 42105 y Fq(a)p Fp(\000)p Fo(3)24570 41906 y Fk(;)g(q)25729 42105 y Fo(1)26256 41906 y Fk(;)g Fg(\001)g(\001)g(\001)444 b Fk(;)221 b(q)29990 42105 y Fq(b)30448 41906 y Fk(;)g(r)31616 42105 y Fo(1)32143 41906 y Fk(;)g(r)33311 42105 y Fo(2)33837 41906 y Fk(;)g(r)35005 42105 y Fo(3)35532 41906 y Fg(g)800 44840 y Fl(are)442 b(distinct.)604 b(The)442 b(n)-36 b(um)g(b)36 b(er)441 b(of)i(suc)-36 b(h)441 b(sets)i(is)f(obtained)g(b)-36 b(y)442 b(m)-36 b(ultiplying)443 b(the)e(b)36 b(ounds)441 b(\()p 0 .5 0 TeXcolorrgb 45340 44840 a SDict begin H.S end 45340 44840 a 0 .5 0 TeXcolorrgb Fl(18)p 0 .5 0 TeXcolorrgb 46641 43984 a SDict begin H.R end 46641 43984 a 46641 44840 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.18) cvn H.B /ANN pdfmark end 46641 44840 a Black Fl(\))h(and)f(\()p 0 .5 0 TeXcolorrgb 50632 44840 a SDict begin H.S end 50632 44840 a 0 .5 0 TeXcolorrgb Fl(20)p 0 .5 0 TeXcolorrgb 51933 43984 a SDict begin H.R end 51933 43984 a 51933 44840 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.20) cvn H.B /ANN pdfmark end 51933 44840 a Black Fl(\).)800 46445 y(Th)-36 b(us,)14612 48810 y(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))369 b Fg(\035)20820 47911 y Fk(M)22217 47429 y Fq(k)24 b Fp(\000)p Fo(1)p 20820 48504 3169 54 v 21558 49721 a Fk(p)22211 49337 y Fo(5)p Fq(k)24490 48810 y Fg(\035)32038 47911 y Fk(x)p 26320 48504 12174 54 v 26320 49721 a Fl(exp\()p Fk(p)221 b Fl(log)241 b(2)295 b(+)g(5)p Fk(k)267 b Fl(log)240 b Fk(p)p Fl(\))38627 48810 y Fk(:)800 51879 y Fl(Th)-36 b(us,)501 b(with)487 b Fk(k)45 b(p)461 b Fl(=)f(\(log)241 b Fk(x)p Fl(\))p Fk(=)p Fl(\(log)f(2\),)501 b(our)488 b(task)g(is)g(to)f(c)-36 b(ho)36 b(ose)488 b Fk(k)533 b Fl(and)487 b Fk(p)g Fl(suc)-36 b(h)486 b(that)h Fk(p)p Fl(\(log)241 b(2\))332 b(+)f(5)p Fk(k)267 b Fl(log)240 b Fk(p)800 53484 y Fl(is)514 b(minimal.)821 b(This)514 b(suggests)h(to)f(c)-36 b(ho)36 b(ose)514 b Fk(k)560 b Fl(and)513 b Fk(p)h Fl(suc)-36 b(h)513 b(that)h Fk(k)551 b Fl(=)506 b(\()p Fk(c)36817 53683 y Fo(5)37692 53484 y Fl(+)350 b Fk(o)p Fl(\(1\)\))p Fk(p=)221 b Fl(log)241 b Fk(p)514 b Fl(as)g Fk(p)506 b Fg(!)g(1)p Fl(,)800 55089 y(where)513 b Fk(c)5197 55288 y Fo(5)6226 55089 y Fl(=)504 b(\(log)240 b(2\))p Fk(=)p Fl(5.)817 b(Since)513 b Fk(k)45 b(p)503 b Fl(=)h(\(log)240 b Fk(x)p Fl(\))p Fk(=)221 b Fl(log)241 b(2,)533 b(w)-36 b(e)514 b(need)e(to)h(c)-36 b(ho)36 b(ose)513 b Fk(p)g Fl(suc)-36 b(h)512 b(that)g Fk(p)47333 54607 y Fo(2)47859 55089 y Fk(=)221 b Fl(log)241 b Fk(p)503 b Fl(=)800 56695 y(\()p Fk(c)1866 56894 y Fo(6)2741 56695 y Fl(+)350 b Fk(o)p Fl(\(1\)\)\(log)240 b Fk(x)p Fl(\),)535 b(where)514 b Fk(c)15842 56894 y Fo(6)16874 56695 y Fl(=)505 b(5)p Fk(=)p Fl(\(log)241 b(2\))23255 56213 y Fo(2)23781 56695 y Fl(.)820 b(This)515 b(sho)-36 b(ws)514 b(sho)-36 b(ws)514 b(that)g(w)-36 b(e)514 b(should)g(c)-36 b(ho)36 b(ose)514 b Fk(p)g Fl(close)800 58300 y(to)657 b Fk(y)796 b Fl(=)748 b Fk(c)6363 58499 y Fo(7)6888 58300 y Fl(\(log)240 b Fk(x)221 b Fl(log)241 b(log)g Fk(x)p Fl(\))15304 57818 y Fo(1)p Fq(=)p Fo(2)16770 58300 y Fl(,)713 b(where)656 b Fk(c)22384 58499 y Fo(7)23658 58300 y Fl(=)748 b(\(2)p Fk(:)p Fl(5\))28091 57818 y Fo(1)p Fq(=)p Fo(2)29558 58300 y Fk(=)221 b Fl(log)241 b(2.)1247 b(A)657 b(recen)-36 b(t)655 b(result)h(of)h(Bak)-36 b(er,)713 b(Har-)800 59905 y(man)537 b(and)g(Pin)-36 b(tz)537 b(\(see)h([)p 0 .5 0 TeXcolorrgb 13055 59905 a SDict begin H.S end 13055 59905 a 0 .5 0 TeXcolorrgb Fl(2)p 0 .5 0 TeXcolorrgb 13705 59049 a SDict begin H.R end 13705 59049 a 13705 59905 a SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.BHP) cvn H.B /ANN pdfmark end 13705 59905 a Black Fl(]\))g(sa)-36 b(ys)538 b(that)f(for)h(large)h Fk(x)e Fl(it)h(is)g(alw)-36 b(a)g(ys)539 b(p)36 b(ossible)537 b(to)h(c)-36 b(ho)36 b(ose)538 b(a)g(prime)f Fk(p)g Fl(in)800 61510 y([)p Fk(c)1721 61709 y Fo(7)2247 61510 y Fl(\(log)240 b Fk(x)221 b Fl(log)241 b(log)f Fk(x)p Fl(\))10662 61028 y Fo(1)p Fq(=)p Fo(2)12129 61510 y Fk(;)221 b(c)13271 61709 y Fo(7)13797 61510 y Fl(\(log)241 b Fk(x)221 b Fl(log)241 b(log)f Fk(x)p Fl(\))22213 61028 y Fo(1)p Fq(=)p Fo(2)23894 61510 y Fl(+)214 b Fk(O)36 b Fl(\(\(log)240 b Fk(x)p Fl(\))30308 61028 y Fo(0)p Fq(:)p Fo(26)32036 61510 y Fl(\)],)402 b(whic)-36 b(h)393 b(is)i(go)36 b(o)g(d)394 b(enough)g(for)g(our)f(pur-)800 63115 y(p)36 b(oses.)549 b(In)344 b(fact,)364 b(the)344 b(statemen)-36 b(t)344 b(that)g(for)h(large)h Fk(x)e Fl(there)g(exists)i(a)f(prime)f(in)g(an)h (in)-36 b(terv)-72 b(al)345 b(lik)-36 b(e)345 b(the)f(ab)36 b(o)-36 b(v)g(e)800 64720 y(with)504 b(the)f(exp)36 b(onen)-36 b(t)503 b(0)p Fk(:)p Fl(26)i(replaced)e(b)-36 b(y)504 b(an)-36 b(y)504 b(exp)36 b(onen)-36 b(t)503 b Fk(<)488 b Fl(1)p Fk(=)p Fl(2)504 b(is)g(go)36 b(o)g(d)505 b(enough)e(for)h(our) g(purp)36 b(oses.)800 66325 y(Once)343 b(suc)-36 b(h)343 b Fk(p)g Fl(is)i(c)-36 b(hosen,)361 b(w)-36 b(e)344 b(c)-36 b(ho)36 b(ose)344 b Fk(k)414 b Fg(\021)369 b Fl(1)591 b(\(mo)36 b(d)443 b(4\))343 b(suc)-36 b(h)343 b(that)h Fk(k)414 b Fl(=)368 b(\(log)240 b Fk(x)p Fl(\))p Fk(=)p Fl(\()p Fk(p)221 b Fl(log)241 b(2\))112 b(+)g Fk(O)36 b Fl(\(1\),)361 b(whic)-36 b(h)p Black 26475 70521 a(9)p Black eop end end %%Page: 10 10 TeXDict begin HPSdict begin 10 9 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.10) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 1328 x Fl(is)527 b(ob)-36 b(viously)528 b(p)36 b(ossible.)858 b(Since)526 b Fk(k)573 b Fg(\034)528 b Fk(p=)221 b Fl(log)241 b Fk(p)p Fl(,)550 b(it)526 b(follo)-36 b(ws)529 b(that)d(the)g(condition)h Fk(k)572 b Fl(=)527 b Fk(o)p Fl(\()p Fk(p)p Fl(\))g(is)g(indeed)800 -1067 y(ful\014lled)434 b(as)g Fk(p)368 b Fg(!)i(1)p Fl(.)579 b(This)433 b(argumen)-36 b(t)433 b(sho)-36 b(ws)434 b(that)27385 -2672 y SDict begin H.S end 27385 -2672 a 27385 -2672 a SDict begin 14.5 H.A end 27385 -2672 a 27385 -2672 a SDict begin [ /View [/XYZ H.V] /Dest (equation.21) cvn H.B /DEST pdfmark end 27385 -2672 a 13479 1867 a Fl(#)p Ff(B)p Fl(\()p Fk(x)p Fl(\))369 b Fg(\025)g Fk(x)221 b Fl(exp)q(\(\()p Fg(\000)p Fk(c)24812 2066 y Fo(8)25633 1867 y Fl(+)295 b Fk(o)p Fl(\(1\)\)\(log)240 b Fk(x)221 b Fl(log)241 b(log)f Fk(x)p Fl(\))38148 1318 y Fo(1)p Fq(=)p Fo(2)39615 1867 y Fl(\))10367 b(\(21\))800 4800 y(holds)433 b(as)h Fk(x)369 b Fg(!)h(1)p Fl(,)434 b(where)f Fk(c)15046 4999 y Fo(8)15941 4800 y Fl(=)369 b(2\(log)240 b(2\))p Fk(c)22095 4999 y Fo(7)22990 4800 y Fl(=)24371 3701 y Fg(p)p 25478 3701 1301 54 v 1099 x Fl(10.)579 b(This)433 b(\014nishes)g(the)g(pro)36 b(of)434 b(of)h(Theorem)p 0 .5 0 TeXcolorrgb 47863 4800 a SDict begin H.S end 47863 4800 a 0 .5 0 TeXcolorrgb Fl(2)p 0 .5 0 TeXcolorrgb 48514 3944 a SDict begin H.R end 48514 3944 a 48514 4800 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (prop.2) cvn H.B /ANN pdfmark end 48514 4800 a Black Fl(.)800 7070 y Fe(Remark.)563 b Fl(Ob)-36 b(viously)-108 b(,)398 b(our)387 b(argumen)-36 b(ts)387 b(for)i(the)e(upp)36 b(er)386 b(b)36 b(ound)387 b(\()p 0 .5 0 TeXcolorrgb 34107 7070 a SDict begin H.S end 34107 7070 a 0 .5 0 TeXcolorrgb Fl(17)p 0 .5 0 TeXcolorrgb 35407 6214 a SDict begin H.R end 35407 6214 a 35407 7070 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.17) cvn H.B /ANN pdfmark end 35407 7070 a Black Fl(\))h(and)f(lo)-36 b(w)g(er)389 b(b)36 b(ound)386 b(\()p 0 .5 0 TeXcolorrgb 46605 7070 a SDict begin H.S end 46605 7070 a 0 .5 0 TeXcolorrgb Fl(21)p 0 .5 0 TeXcolorrgb 47906 6214 a SDict begin H.R end 47906 6214 a 47906 7070 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.21) cvn H.B /ANN pdfmark end 47906 7070 a Black Fl(\))h(are)h(not)800 8675 y(tigh)-36 b(t)408 b(and)h(at)g(least)g(the) f(in)-36 b(v)g(olv)g(ed)409 b(m)-36 b(ultiplicativ)g(e)410 b(constan)-36 b(ts)408 b(inside)h(the)f(exp)36 b(onen)-36 b(tials)409 b(can)g(easily)h(b)36 b(e)800 10280 y(impro)-36 b(v)g(ed.)552 b(W)-108 b(e)353 b(lea)-36 b(v)g(e)355 b(it)f(to)f(the)h(reader)f(as)h(an)f(op)36 b(en)354 b(problem)f(to)h (bring)f(the)g(upp)36 b(er)353 b(and)g(lo)-36 b(w)g(er)354 b(b)36 b(ounds)800 11885 y(\()p 0 .5 0 TeXcolorrgb 1306 11885 a SDict begin H.S end 1306 11885 a 0 .5 0 TeXcolorrgb Fl(17)p 0 .5 0 TeXcolorrgb 2607 11029 a SDict begin H.R end 2607 11029 a 2607 11885 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.17) cvn H.B /ANN pdfmark end 2607 11885 a Black Fl(\))433 b(and)g(\()p 0 .5 0 TeXcolorrgb 6581 11885 a SDict begin H.S end 6581 11885 a 0 .5 0 TeXcolorrgb Fl(21)p 0 .5 0 TeXcolorrgb 7881 11029 a SDict begin H.R end 7881 11029 a 7881 11885 a SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.21) cvn H.B /ANN pdfmark end 7881 11885 a Black Fl(\))h(substan)-36 b(tially)434 b(closer.)800 14219 y SDict begin H.S end 800 14219 a 800 14219 a SDict begin 14.5 H.A end 800 14219 a 800 14219 a SDict begin [ /View [/XYZ H.V] /Dest (section.4) cvn H.B /DEST pdfmark end 800 14219 a 2103 x Fm(4)2152 b(Ac)-60 b(kno)g(wledgemen)g (ts)800 19242 y Fl(W)-108 b(e)290 b(thank)g(the)g(referee)g(for)h(a)g (careful)f(reading)h(of)g(the)e(man)-36 b(uscript)289 b(and)h(for)h(suggestions)g(that)e(impro)-36 b(v)g(ed)800 20848 y(the)525 b(qualit)-36 b(y)527 b(of)f(our)f(pap)36 b(er.)854 b(This)526 b(pap)36 b(er)525 b(started)g(during)f(a)i (pleasan)-36 b(t)526 b(visit)g(of)g(the)f(second)h(author)800 22453 y(at)494 b(the)g(Mathematical)g(Institute)g(of)g(the)g(UNAM)g(in) g(Morelia,)510 b(Mexico)495 b(in)f(No)-36 b(v)g(em)g(b)36 b(er)494 b(of)h(2007.)761 b(He)800 24058 y(thanks)354 b(the)g(p)36 b(eople)355 b(of)g(this)f(Institute)g(for)g(their)g (hospitalit)-36 b(y)-108 b(.)553 b(During)354 b(the)g(preparation)g(of) h(this)f(pap)36 b(er,)800 25663 y(F.)434 b(L.)f(w)-36 b(as)434 b(supp)36 b(orted)433 b(in)g(part)g(b)-36 b(y)434 b(Gran)-36 b(t)432 b(SEP-CONA)-36 b(CyT)434 b(79685)h(and)e(P)-108 b(API)36 b(IT)434 b(100508.)800 30100 y Fm(References)800 31415 y SDict begin H.S end 800 31415 a 800 31415 a SDict begin 14.5 H.A end 800 31415 a 800 31415 a SDict begin [ /View [/XYZ H.V] /Dest (section*.1) cvn H.B /DEST pdfmark end 800 31415 a 800 30862 a SDict begin H.S end 800 30862 a 800 30862 a SDict begin 14.5 H.A end 800 30862 a 800 30862 a SDict begin [ /View [/XYZ H.V] /Dest (cite.Ay) cvn H.B /DEST pdfmark end 800 30862 a Black 2751 33020 a Fl([1])p Black 651 w(R.)684 b(Ay)-36 b(oub,)360 b(On)340 b(Rademac)-36 b(her's)342 b(extension)g(of)g(the)f(Goldbac)-36 b(h-Vinogrado)g(v)341 b(theorem,)360 b Fh(Canad.)4774 34626 y(J.)465 b(Math.)433 b Fe(5)g Fl(\(1953\),)i(482{491.)800 35511 y SDict begin H.S end 800 35511 a 800 35511 a SDict begin 14.5 H.A end 800 35511 a 800 35511 a SDict begin [ /View [/XYZ H.V] /Dest (cite.BHP) cvn H.B /DEST pdfmark end 800 35511 a Black 2751 37338 a Fl([2])p Black 651 w(R.)463 b(C.)h(Bak)-36 b(er,)470 b(G.)925 b(Harman)463 b(and)f(J.)926 b(Pin)-36 b(tz,)470 b(The)462 b(di\013erence)g(b)36 b(et)-36 b(w)g(een)462 b(consecutiv)-36 b(e)463 b(primes.)4774 38943 y(I)36 b(I.,)435 b Fh(Pr)-66 b(o)g(c.)464 b(L)-66 b(ond.)464 b(Math.)g(So)-66 b(c.)432 b Fl(I)36 b(I)g(I)435 b(Ser.)e Fe(83)h Fl(\(2001\),)h(532{562.)800 39828 y SDict begin H.S end 800 39828 a 800 39828 a SDict begin 14.5 H.A end 800 39828 a 800 39828 a SDict begin [ /View [/XYZ H.V] /Dest (cite.BaLu) cvn H.B /DEST pdfmark end 800 39828 a Black 2751 41655 a Fl([3])p Black 651 w(W.)465 b(D.)g(Banks)g(and)e(F.)i (Luca,)471 b(Sums)464 b(of)h(prime)e(divisors)j(and)d(Mersenne)h(n)-36 b(um)g(b)36 b(ers,)470 b Fh(Houston)4774 43260 y(J.)465 b(Math.)433 b Fe(33)h Fl(\(2007\),)g(403{413.)800 44145 y SDict begin H.S end 800 44145 a 800 44145 a SDict begin 14.5 H.A end 800 44145 a 800 44145 a SDict begin [ /View [/XYZ H.V] /Dest (cite.Ba) cvn H.B /DEST pdfmark end 800 44145 a Black 2751 45972 a Fl([4])p Black 651 w(C.)584 b(Bauer,)622 b(On)582 b(Goldbac)-36 b(h's)583 b(conjecture)h(in)f (arithmetic)h(progressions,)621 b Fh(Studia)603 b(Sci.)e(Math.)4774 47577 y(Hungar.)433 b Fe(37)h Fl(\(2001\),)h(1{20.)800 48463 y SDict begin H.S end 800 48463 a 800 48463 a SDict begin 14.5 H.A end 800 48463 a 800 48463 a SDict begin [ /View [/XYZ H.V] /Dest (cite.CEP) cvn H.B /DEST pdfmark end 800 48463 a Black 2751 50289 a Fl([5])p Black 651 w(E.)413 b(R.)g(Can\014eld,)j(P)-108 b(.)413 b(Erd})-650 b(os)412 b(and)f(C.)i(P)-36 b(omerance,)417 b(On)412 b(a)h(problem)e(of)j(Opp)36 b(enheim)410 b(concerning)4774 51894 y(\\factorisatio)436 b(n)-36 b(umerorum",)433 b Fh(J.)464 b(Numb)-66 b(er)464 b(The)-66 b(ory)549 b Fe(17)434 b Fl(\(1983\),)h(1{28.)800 52780 y SDict begin H.S end 800 52780 a 800 52780 a SDict begin 14.5 H.A end 800 52780 a 800 52780 a SDict begin [ /View [/XYZ H.V] /Dest (cite.KoLu1) cvn H.B /DEST pdfmark end 800 52780 a Black 2751 54606 a Fl([6])p Black 651 w(J.-M.)961 b(De)f(Koninc)-36 b(k)481 b(and)e(F.)961 b(Luca,)491 b(On)480 b(p)36 b(ositiv)-36 b(e)481 b(in)-36 b(tegers)480 b Fk(n)g Fl(whic)-36 b(h)480 b(are)g(divisible)i(b)-36 b(y)480 b(the)4774 56211 y(sum)433 b(of)i(their)e(prime)g(factors,)i Fh(Mathematika)531 b Fe(52)434 b Fl(\(2005\),)h(69{77.)800 57097 y SDict begin H.S end 800 57097 a 800 57097 a SDict begin 14.5 H.A end 800 57097 a 800 57097 a SDict begin [ /View [/XYZ H.V] /Dest (cite.KoLu2) cvn H.B /DEST pdfmark end 800 57097 a Black 2751 58923 a Fl([7])p Black 651 w(J.-M.)830 b(De)g(Koninc)-36 b(k)416 b(and)e(F.)830 b(Luca,)419 b(In)-36 b(tegers)414 b(divisible)i(b)-36 b(y)415 b(sums)g(of)g(p)36 b(o)-36 b(w)g(ers)415 b(of)h(their)e(prime)4774 60528 y(factors,)435 b Fh(J.)464 b(Numb)-66 b(er)464 b(The)-66 b(ory)550 b Fe(128)434 b Fl(\(2008\),)h(557{563.)800 61414 y SDict begin H.S end 800 61414 a 800 61414 a SDict begin 14.5 H.A end 800 61414 a 800 61414 a SDict begin [ /View [/XYZ H.V] /Dest (cite.KoLu3) cvn H.B /DEST pdfmark end 800 61414 a Black 2751 63240 a Fl([8])p Black 651 w(J.-M.)897 b(De)h(Koninc)-36 b(k)448 b(and)g(F.)897 b(Luca,)452 b(On)c(sums)g(of)h(p)36 b(o)-36 b(w)g(ers)449 b(of)g(prime)f(factors)h (of)h(an)e(in)-36 b(teger,)4774 64846 y Fh(A)j(nn.)463 b(Univ.)g(Sci.)g(Budap)-66 b(est)466 b(Se)-66 b(ct.)463 b(Comput.)p Fl(,)433 b(to)h(app)36 b(ear.)p Black 26150 70521 a(10)p Black eop end end %%Page: 11 11 TeXDict begin HPSdict begin 11 10 bop 0 0 a SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end 0 0 a Black 0 TeXcolorgray 800 -4000 a SDict begin H.S end 800 -4000 a 0 TeXcolorgray 0 TeXcolorgray 800 -4000 a SDict begin H.R end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (page.11) cvn H.B /DEST pdfmark end 800 -4000 a Black Black 800 -4000 a SDict begin H.S end 800 -4000 a 800 -4000 a SDict begin 14.5 H.A end 800 -4000 a 800 -4000 a SDict begin [ /View [/XYZ H.V] /Dest (cite.ErPom) cvn H.B /DEST pdfmark end 800 -4000 a Black 2751 -2672 a Fl([9])p Black 651 w(P)-108 b(.)387 b(Erd})-650 b(os)387 b(and)f(C.)i(P)-36 b(omerance,)397 b(On)386 b(the)g(largest)i(prime)f (factors)g(of)h Fk(n)g Fl(and)e Fk(n)200 b Fl(+)g(1,)397 b Fh(A)-66 b(e)g(quationes)4774 -1067 y(Math.)433 b Fe(17)h Fl(\(1978\),)h(311{321.)800 -181 y SDict begin H.S end 800 -181 a 800 -181 a SDict begin 14.5 H.A end 800 -181 a 800 -181 a SDict begin [ /View [/XYZ H.V] /Dest (cite.LuPo) cvn H.B /DEST pdfmark end 800 -181 a Black 2101 1645 a Fl([10])p Black 651 w(F.)422 b(Luca)f(and)g(C.)h(P)-36 b(omerance,)424 b(Irreducible)d(radical)h(extensions)g(and)f (Euler-function)f(c)-36 b(hains,)4774 3251 y(in)434 b Fh(Combinatorial)463 b(Numb)-66 b(er)464 b(The)-66 b(ory)p Fl(,)433 b(de)g(Gruyter,)g(Berlin,)h(2007,)h(pp.)e(351{361.)800 4062 y SDict begin H.S end 800 4062 a 800 4062 a SDict begin 14.5 H.A end 800 4062 a 800 4062 a SDict begin [ /View [/XYZ H.V] /Dest (cite.Pom1) cvn H.B /DEST pdfmark end 800 4062 a Black 2101 5963 a Fl([11])p Black 651 w(C.)525 b(Nelson,)548 b(D.)525 b(E.)f(P)-36 b(enney)524 b(and)g(C.)h(P)-36 b(omerance,)547 b(714)525 b(and)f(715,)548 b Fh(J.)g(R)-66 b(e)g(c.)546 b(Math.)523 b Fe(7)i Fl(\(1974\),)4774 7568 y(87{89.)800 8121 y SDict begin H.S end 800 8121 a 800 8121 a SDict begin 14.5 H.A end 800 8121 a 800 8121 a SDict begin [ /View [/XYZ H.V] /Dest (cite.Pom2) cvn H.B /DEST pdfmark end 800 8121 a Black 2101 10280 a Fl([12])p Black 651 w(C.)510 b(P)-36 b(omerance,)529 b(Ruth-Aaron)508 b(n)-36 b(um)g(b)36 b(ers)507 b(revisited,)529 b(in)509 b Fh(Paul)536 b(Er)-66 b(d})-664 b(os)535 b(and)f(his)h(Mathematics)p Fl(,)4774 11885 y(Boly)-36 b(ai)436 b(So)36 b(c.)433 b(Math.)h(Stud.)e Fe(11)p Fl(,)j(Janos)f(Boly)-36 b(ai)435 b(Math.)e(So)36 b(c.,)434 b(Budap)36 b(est,)434 b(2002,)h(567{579.)p 800 14955 52000 45 v 800 17206 a(2000)g Fh(Mathematics)464 b(Subje)-66 b(ct)463 b(Classi\014c)-66 b(ation)p Fl(:)577 b(Primary)434 b(11A41;)h(Secondary)e(11N25.)800 18811 y Fh(Keywor)-66 b(ds:)1250 b Fl(primes,)434 b(siev)-36 b(e)434 b(metho)36 b(ds.)p 800 20442 V 800 22766 a(\(Concerned)433 b(with)h(sequence)p 0 1 0 0 TeXcolorcmyk 16090 23032 a SDict begin H.S end 16090 23032 a 0 1 0 0 TeXcolorcmyk -266 x Fl(A156787)p 16090 22979 4878 54 v 0 1 0 0 TeXcolorcmyk 20967 21859 a SDict begin H.R end 20967 21859 a 20967 22766 a SDict begin [ /H /I /Border [0 0 0] /Color [0 1 1] /Action << /Subtype /URI /URI (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A156787) >> /Subtype /Link H.B /ANN pdfmark end 20967 22766 a Black Fl(.\))p 800 24471 52000 45 v 800 27522 a(Receiv)-36 b(ed)336 b(Decem)-36 b(b)36 b(er)336 b(15)g(2008;)370 b(revised)336 b(v)-36 b(ersion)336 b(receiv)-36 b(ed)336 b(F)-108 b(ebruary)334 b(20)j(2009.)547 b(Published)334 b(in)i Fh(Journal)800 29127 y(of)465 b(Inte)-66 b(ger)462 b(Se)-66 b(quenc)g(es)p Fl(,)432 b(F)-108 b(ebruary)433 b(23)h(2009.)p 800 30758 V 800 33009 a(Return)f(to)p 0 1 0 0 TeXcolorcmyk 6815 33267 a SDict begin H.S end 6815 33267 a 0 1 0 0 TeXcolorcmyk -258 x Fl(Journal)h(of)g(In) -36 b(teger)434 b(Sequences)f(home)g(page)p 0 1 0 0 TeXcolorcmyk 29602 32086 a SDict begin H.R end 29602 32086 a 29602 33009 a SDict begin [ /H /I /Border [0 0 0] /Color [0 1 1] /Action << /Subtype /URI /URI (http://www.cs.uwaterloo.ca/journals/JIS/) >> /Subtype /Link H.B /ANN pdfmark end 29602 33009 a Black Fl(.)p Black 26150 70521 a(11)p Black eop end end %%Trailer end