Prime Factors, Modular Arithmetic, and Using PariDate: 08/08/2007 at 05:14:39 From: James Subject: arithmetic progression problem For some reason, I'm finding this problem (which appears to be quite innocent) to be very difficult. Can someone here please help? Suppose we have two positive integers 'a' and 'b'. Is there a sufficient method to find a positive integer 'k', such that a + bk = x^2 for some integer 'x'. In other words, how can we find a positive integer 'k', such that 'a + bk' is a square. I'm thinking that this problem might be difficult because it may involve elliptic functions, and thus can only be solved using some very advanced mathematical techniques (I'm not sure though). In any case, if there is no simple method for doing this, then I don't suppose anyone here knows of say a probabilistic procedure for determining a positive integer 'k' that has this property. Thanks a bunch. Date: 08/08/2007 at 11:10:24 From: Doctor Vogler Subject: Re: arithmetic progression problem Hi James, Thanks for writing to Dr. Math. It doesn't require elliptic functions, but some modular arithmetic is very helpful. Mod, Modulus, Modular Arithmetic http://mathforum.org/library/drmath/view/62930.html For some (a, b) pairs, there are no solutions. This happens precisely when a is not a quadratic residue (i.e. a square) mod b. You can compute whether this is the case for some (a, b) using the Legendre symbol and the Law of Quadratic Reciprocity. When a is a quadratic residue mod b, that means that there is at least one solution x^2 = a (mod b), which means that x^2 - a = bk for some integer k, and this is exactly what you want. You can find all numbers x between 0 and b-1 that have x^2 = a (mod b) if you can factor b, then you can add any integer multiple of b to x, and these will give all solutions for x, and therefore all solutions for k as well. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 08/08/2007 at 17:44:13 From: James Subject: arithmetic progression problem Thanks Dr. Vogler. All right, so basically I just look at all the numbers 'x' between 0 and b-1 which have the property x^2 = a mod b. Unfortunately, the numbers (a,b) that I happen to be interested in are very big, so checking up to b-1 values is undesirable. For example, one pair of numbers that I'm currently interested in is when 19,825 + 185648k = x^2 for some integer 'x'. Obviously I don't wish to check all 185,648 numbers from 0-185,647. Are there tricks I can use based on the specific values of (a,b) that would allow me to find a desired 'k' value very quickly (i.e. not have to check all b-1 numbers). Furthermore, what if instead of finding when a + kb = x^2, for some given (a,b), I wanted to know when the quadratic k^2 + ak + b = x^2 (i.e. given (a,b), what integer k causes k^2 + ak + b to be equal to a square). Again, keep in mind that I'm interested in cases when the pair of integers (a,b) happen to be very large. I think I might be asking some pretty tough questions here. Please only answer what you can. However if you know of some mathematical topic that deals with problems such as this, then could you please provide me with a link to it? Oh yeah, one more thing (this will probably simplify things a lot). I'm not necessarily interested in finding all values 'k' that satisfy the property a + bk = x^2, or k^2 + ak + b = x^2 given (a,b). In fact, if you could tell me how I might be able to find the first or smallest, integer k, that satisfies this property, that would be just fine. Date: 08/08/2007 at 22:34:25 From: Doctor Vogler Subject: Re: arithmetic progression problem As James wrote to Dr. Math: >Are there tricks I can use based on the specific values of (a,b) >that would allow me to find a desired 'k' value very quickly (ie not >have to check all b-1 numbers). Hi James, Yes, there are. You may recall that I said you could find all x values as long as you can factor b. This is a standard trick in modular arithmetic. In your case, b = 185648 = 2^4 * 41 * 283. Then you solve for x mod each of these factors: x^2 = 19825 (mod 283) x^2 = 19825 (mod 41) x^2 = 19825 (mod 16). You can use a Legendre symbol computation to decide if 19825 is a square mod each of these factors, which is about as fast as a GCD (which is pretty fast). It is a square mod 283, and mod 16, but not mod 41. Since it's not a square mod 41, it's also not a square mod any multiple of 41, and therefore there are no solutions for a=19825 and b=185648. If it is a square mod each of those factors, then you can compute one of the square roots mod each factor using the Tonelli-Shanks algorithm (or various other algorithms). For example, you could compute that 79^2 = 19825 (mod 283) 1^2 = 19825 (mod 16). The following applies to nonzero squares in modular arithmetic: If you have one square root x mod p (for an odd prime number p), then all square roots will be either x mod p or -x mod p. If you have an odd prime power in the factorization of b, then you can get from a square root x mod p to a square root mod p^2 using Newton's Method. (You didn't know that helped in modular arithmetic, did you?) Repeat to get square roots mod higher powers of p. Again, there are exactly two square roots mod p^n (negatives of one another) for any positive integer n and any odd prime p. When you have a large power of 2 in the prime factorization of b, you get not two but four square roots. Said differently, the square roots of a square s mod 2^n (for n>2) are determined mod 2^(n-1) and are negatives of one another. For example, the square roots of 9 mod 16 are +3 and -3 mod 8 (so 3, 5, 11, and 13 mod 16 all square to 9 mod 16). When you have a square root mod 16, you can use Newton's Method to turn it into a square root mod higher powers of 2. Once you have all of the square roots mod all of the factors of b, you can put them together using the Chinese Remainder Theorem. If you're doing this by hand (not writing a computer program to do it), then I might recommend downloading GNU Pari at http://pari.math.u-bordeaux.fr/ Pari has implemented integer factorization, and Legendre symbol computations, and modular square roots, and the Chinese Remainder Theorem. So let's do an example. 77753 + 116464k = x^2 First we have 77753 = x^2 (mod 116464), so we need to check if 77753 is a square, or else there aren't any solutions at all. In Pari, we can ask issquare(Mod(77753,116464)) and it will factor the modulus 116464 and compute all of the Legendre symbols and finally tell you 1 (which means "yes"; 0 means "no"). Now, Pari won't take the square root with a composite modulus, so we have to factor b. factor(116464) and Pari gives us the factorization 116464 = 2^4 * 29 * 251 (I'll let you see how Pari represents this). Now we need square roots mod 16, 29, and 251. So we ask sqrt(Mod(77753,29)) sqrt(Mod(77753,251)) and we get 2 mod 29 and 52 mod 251, respectively. That means that all square roots are 2 mod 29 and -2 = 27 mod 29, and 52 mod 251 and -52 = 199 mod 251. We can't ask for sqrt(Mod(77753,16)) since 16 is not prime, but 77753 = 9 (mod 16), and I already told you that the square roots are 3 and -3 mod 8. Now there are eight ways to combine these, namely 2 mod 29, 52 mod 251, 3 mod 8 2 mod 29, 52 mod 251, 5 mod 8 2 mod 29, 199 mod 251, 3 mod 8 2 mod 29, 199 mod 251, 5 mod 8 27 mod 29, 52 mod 251, 3 mod 8 27 mod 29, 52 mod 251, 5 mod 8 27 mod 29, 199 mod 251, 3 mod 8 27 mod 29, 199 mod 251, 5 mod 8 Pari can only put two together at a time, so we call the "chinese" function twice for each one: chinese(chinese(Mod(2,29),Mod(52,251)),Mod(3,8)) chinese(chinese(Mod(2,29),Mod(52,251)),Mod(5,8)) chinese(chinese(Mod(2,29),Mod(199,251)),Mod(3,8)) chinese(chinese(Mod(2,29),Mod(199,251)),Mod(5,8)) chinese(chinese(Mod(27,29),Mod(52,251)),Mod(3,8)) chinese(chinese(Mod(27,29),Mod(52,251)),Mod(5,8)) chinese(chinese(Mod(27,29),Mod(199,251)),Mod(3,8)) chinese(chinese(Mod(27,29),Mod(199,251)),Mod(5,8)) Pari gives us 8 numbers mod 58232. That means that x must be one of these 8 numbers plus some integer multiple of 58232. For example, let's take the first one. If x = 1307 + 58232n, then x^2 = 3390965824n^2 + 152218448n + 1708249 and k = (x^2 - 77753)/116464 = 29116n^2 + 1307n + 14. You can get similar formulas for the other 7 solutions. If you'd like to write your own program that does all of this, then I would recommend searching our archives or the Internet for legendre symbol quadratic reciprocity tonelli shanks chinese remainder theorem integer factorization and so forth. Write back if you have questions about these. >Furthermore, what if instead of finding when a + kb = x^2, for some >given (a,b), I wanted to know when the quadratic k^2 + ak + b = x^2 >(i.e. given (a,b), what integer k causes k^2 + ak + b to be equal to >a square). Again, keep in mind that I'm interested in cases when the >pair of integers (a,b) happen to be very large. Surprisingly, this is an easier question! It gets a lot harder if you put a (non-square) coefficient in front of that k^2, but when the coefficient of k^2 is a square, the problem is very straight-forward, and can be solved by the method in Second-Degree Two-Variable Diophantine Equation http://mathforum.org/library/drmath/view/55988.html The idea is to factor the difference of two squares. I'll demonstrate. If a is even, then you complete the square on the left side as (k + a/2)^2 + b - a^2/4 = x^2. In case a is odd, you complete the square after multiplying both sides by 4: (2k + a)^2 + 4b - a^2 = 4x^2, and then you subtract the square on the left and factor the difference of two squares: 4b - a^2 = (2x)^2 - (2k + a)^2 (2x - 2k - a)(2x + 2k + a) = 4b - a^2. Next, you factor the integer 4b - a^2 on the right side of the equation. Then you can list off all of its (integer) factors, and 2x + 2k + a has to be one of these factors. So you try them all and write down the ones that work. Note that there will only be finitely many solutions. When you have a non-square coefficient in front of the k^2, then you have a more challenging quadratic Diophantine equation. To find out how to solve those kinds of equations, you should search our archives or the Internet for quadratic Diophantine equation and Pell equation which is a related topic. In this case, there will be infinitely many solutions. The easy part is getting from the smallest solution (or a small set of small solutions) to larger ones; when the coefficients are large, finding that smallest solution can be quite hard, though a continued fraction algorithm gives a moderately fast way to find it. >Oh yeah, one more thing (this will probably simplify things a lot). >I'm not necessarily interested in finding all values 'k' that >satisfy the property a + bk = x^2, or k^2 + ak + b = x^2 given (a,b). > >In fact, if you could tell me how I might be able to find the first >or smallest, integer k, that satisfies this property, that would be >just fine. Actually, this doesn't really make the problem much easier for most (a,b) pairs. If b is very large and hard to factor, but a is already a square, then you can find some solutions to a + bk = x^2 without finding all of them since you know one of the square roots of a. But finding a square root mod b is usually not significantly easier than finding all square roots mod b. As for k^2 + ak + b = x^2, the easy solutions come from using the factor 1 (or a power of 2), and other solutions require factoring 4b-a^2. For example, if a is odd, then you can solve 2x - 2k - a = 1 2x + 2k + a = 4b - a^2 for x and k and get x = (4b - a^2 + 1)/4 k = (4b - a^2 - 2a - 1)/4 which are integers when a is odd (if a is even, use a power of 2 instead of 1). - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 08/09/2007 at 19:13:35 From: James Subject: arithmetic progression problem Thanks Dr. Vogler for the detailed answer (and for providing that Pari link). I'll get to my question regarding the math we've been discussing in a bit, but I have a couple of questions regarding the Pari program I downloaded. When I was at the site to download Pari, there was a message that said it was strongly recommended that if I intend to compile PARI/GP from a source distribution, then I should also download the GNU readline libraries, so that the gp calculator would go respectively faster. I don't know what this means (or if this even applies to me), however I couldn't figure out how to download GNU readline libraries (however I was able to download GNU MP luckily). In any case, despite whatever potential setbacks that this could cause, I was still able to download Pari and do all the calculations that you listed. Okay, my second question about Pari (and this really doesn't have anything to do with what we're discussing, but is just something I'm curious about). I tried factorizing the number RSA-129 (which is a 129 digit number that is the product of only two primes), however after I plugged in the first 50 digits or so, something happened, and the "factor" command no longer appeared, and I had to continue filling in the remaining digits on the next line. Then when I went to press the 'ENTER' command, nothing happened (i.e. it didn't factorize). Anyway, I'll list the number for you (maybe you'll have better luck with this than I): 114,381,625,757,888,867,669,235,779,976,146,612,010,218,296,721,242,3 62,562,561,842,935,706,935,245,733,897,830,597,123,563,958,705,058,98 9,075,147,599,290,026,879,543,541 Okay, regarding the actual math problem which I was originally asking about, you said that for k^2+ak+b=x^2, the easy solutions come from using the factor 1 (or a power of 2). I'm interested in the case when you have to use a power of two (for when 'a' is even). I'm not sure I'm interpreting you correctly, since I tried doing this for when a = 185,648 and b = -165,823 from which we get a^2/4 - b = 8,616,460,799 and a/2 = 92,824. Thus using a power of two, say 4, we find that we have to solve (k+92,824-x)=4 (k+92,824+x)= 8,616,460,799. Plugging k=x-92,820 into the second equation and then solving for x, gives us x=(8,616,460,795)/2 This is obviously not an integer because the numerator is not even. So what am I doing wrong? I'm interested in finding solutions for x and k this way because the other solutions require me factorizing 8,616,460,799, which as you can tell is no simple task. (By hand anyway. The Pari program you provided was able to do it instantly.) I have one more question regarding how Newton's method can be used to find square roots, since I didn't understand how this could be done given your last message. Are you talking about the same Newtonian method that is described in calculus? Again, just answer what you can, or as much as time allows. Thanks a bunch. James PS: The Pari program seems pretty impressive, and its very fast. It has inspired me to ask another question on the Ask Dr. Math site, regarding the potential of using technology to solve very difficult math problems. Date: 08/09/2007 at 20:18:56 From: Doctor Vogler Subject: Re: arithmetic progression problem As James wrote to Dr. Math >When I was at the site to download Pari, there was a message that >said it was strongly recommended that if I intend to compile PARI/GP >from a source distribution, then I should also download the GNU >readline libraries, so that the gp calculator would go respectively >faster. I don't know what this means (or if this even applies to >me), however I couldn't figure out how to download GNU readline >libraries ( however I was able to download GNU MP luckily). In any >case, despite whatever potential setbacks that this could cause, I >was still able to download Pari and do all the calculations that you >listed. Hi James, That applies if you want to compile it yourself instead of just installing the program. If you're running Windows, then it's easiest to just download the Windows binary and install. If you're running UNIX, then you probably wouldn't have had to ask. >Okay, my second question about Pari (and this really doesn't have >anything to do with what were discussing, but is just something I'm >curious about). I tried factorizing the number RSA-129 (which is a >129 digit number that is the product of only two primes), however >after I plugged in the first 50 digits or so, something happened, >and the "factor" command no longer appeared, and I had to continue >filling in the remaining digits on the next line. Then when I went >to press the 'ENTER' command, nothing happened (i.e. it didn't >factorize). Anyway, I'll list the number for you (maybe you'll have >better luck with this than I) > >114,381,625,757,888,867,669,235,779,976,146,612,010,218,296,721,242,3 >62,562,561,842,935,706,935,245,733,897,830,597,123,563,958,705,058,98 >9,075,147,599,290,026,879,543,541 When your typing is longer than one line, it will push the line to the left, so part of the command won't be displayed. But Pari still knows it, so you should just keep typing. Try it with a 1 followed by lots of zeros first (which is easy to factor) to make sure you and Pari are communicating well. Then try RSA-129 again, and be aware that it will take Pari a LONG time to factor. (Remember: That's the point of RSA challenges; these numbers are hard to factor.) >Okay, regarding the actual math problem which I was originally asking >about, you said that for k^2+ak+b=x^2, the easy solutions come from >using the factor 1 (or a power of 2). I'm interested in the case >when you have to use a power of two (for when 'a' is even). I'm not >sure I'm interpreting you correctly, since I tried doing this for >when a = 185,648 and b = -165,823 from which we get a^2/4 - b = >8,616,460,799 and a/2 = 92,824. Thus using a power of two, say 4, we >find that we have to solve > >(k+92,824-x)=4 >(k+92,824+x)= 8,616,460,799. > >Plugging k=x-92,820 into the second equation and then solving for x, >gives us > >x=(8,616,460,795)/2 > >This is obviously not an integer because the numerator is not even. >So what am I doing wrong? I'm interested in finding solutions for x >and k this way because the other solutions require me factorizing >8,616,460,799, which as you can tell is no simple task (By hand >anyway. The Pari program you provided was able to do it instantly). Your equation is (k + 92,824)^2 - x^2 = 8,616,460,799 or (k + 92,824 - x) * (k + 92,824 + x) = 8,616,460,799, which means that the first factor must be a factor of 8,616,460,799, and 4 is not a factor of 8,616,460,799. But 1 is. Recall that in my last email I had factored the general equation as (2x - 2k - a)(2x + 2k + a) = 4b - a^2, and if a was even, then you wouldn't want to let the first factor be 1, because then the second factor would have to be even (since 4b-a^2 is even), but the two factors sum to a multiple of 4 (4x, in fact), so that wouldn't give you an integer solution. In this case, you would be better off using 2 for your first factor instead of 1. >I have one more question regarding how Newton's method can be used >to find square roots, since I didn't understand how this could be >done given your last message. Are you talking about the same >Newtonian method that is described in calculus? Let's suppose you want to find a square root of 5 mod 41^8. First you have to find a square root of 5 mod 41. So you ask Pari and you get 13 (or you could use its negative 28). Set x = 13, and then use Newton's Method on f(x) = x^2 - 5 doing your computations mod 41^2. You get x_2 = 13 - (13^2 - 5)/(2*13) (mod 41^2). You can even ask Pari, Mod(13,41^2) - (13^2 - 5)/(2*13) and it will do the modular inverse for you and give Mod(136, 1681) which is a square root of 5 mod 41^2 (and is congruent to 13 mod 41). Then you do it again mod 41^4 and get x_3 = 136 - (136^2 - 5)/(2*136) (mod 41^4) and you get Mod(1444115, 2825761) which is a square root of 5 mod 41^4. Repeating one more time, you finally get Mod(1843547700842, 7984925229121) which is a square root of 5 mod 41^8. (Try %^2, which means "last answer" squared. You might also find the command "lift(%)" useful, as "lift" removes the "Mod" and when you want to do a higher power of 41, you have to remove the Mod. Also try "?" and look in the manual.) >PS: The Pari program seems pretty impressive, and its very fast. It >has inspired me to ask another question on the Ask Dr. Math site, >regarding the potential of using technology to solve very difficult >math problems. Oh, I use computers all the time. I would highly recommend them. Pari is one of my favorite math programs, though I use magma for certain complicated functions and Mathematica for certain kinds of polynomial or list manipulations. I've used Maple in the past and Matlab hardly at all (though both have important uses). I've also written many programs of my own to do various simple (or not so simple) computations that I couldn't get a math program to do like I wanted. But computers have their limitations, too. You have to tell it how to solve the problem, so you have to know some math in order for it to be useful. And it (generally) can't prove theorems. Sometimes, a minute or two of mathematical logic can save hours of computation time. And suppose you wanted to find all solutions to your quadratic equation. You can't ask the computer to try all pairs (k, x) of integers, because there are infinitely many of them! But a little mathematical thought will allow you to simplify the problem into one that a computer can manage: Factor an integer, and then run through its factors. (Speaking of running through its factors, try "?fordiv" in Pari.) - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 08/10/2007 at 20:33:22 From: James Subject: arithmetic progression problem Hi Dr. Vogler, I tried using that "fordiv" function by typing in something like (100,X,seq) but I got a message saying something like "expected character". Also I have another short little question for you that I've been having trouble answering. Suppose I have a composite number N. Is there sufficient method (other than just trial and error) I can use that will enable me to find a number 'b' such that when I divide N by 'b', I get a number that is divisible by 'b+1'? For example, consider the number 2020. In this instance the only number that seems to work is when b=42, since 2020-42/43=46. Of course the only way I could figure this out was by mainly by trial and error (subtracting even numbers from 2020 and seeing if it is divisible by a number 1 greater than the number I subtracted). Here's a bit of incentive. If you can tell me of a quick way to do this, then I can give you a quick way to factor even the hardest and biggest composite numbers into their primes. Recently I've taken out a couple of books on factoring composite numbers into their primes. It seems that trying to factorize composites by finding quadratic module residues has been attempted before. I'm interested in using Pari to test how efficient an algorithm I made is for generating sequences of primes. My reason being, is that I'm interested in trying to factorize RSA numbers. However because RSA numbers are usually only divisible by HUGE unknown prime numbers, I'm interested in finding sequences of primes that have a specific range in its number of digits. Anyway, I'm not sure how good this algorithm is, as it seems to take longer if we want to find sequences of BIG primes. Thus I'm interested in using Pari to tell me how accurate it is. Seeing as how you seem to engage in these sort of projects, I was wondering if you could tell me if its possible for Pari to do this, and if not then what program can do. Okay, here it is. Consider the product 2*3*5*7*11.....p, i.e. the product of all primes from to 2 to some prime number p. Now I wish to generate the sequence of primes numbers above this product (2*3*5....*p) by adding on the sequence of primes greater than p. For example consider the product 2*3*5*7=210. In this case p=7, so we wish to start adding primes to this product, starting from 11, i.e. 210+11=221 210+13=223 210+17=227 210+19=229 210+23=233 210+29=239 210+31=241 Notice that all of these numbers are prime except for 221, and that these prime numbers are consecutive (i.e. there isn't another prime number between any two of these primes). We can do a similar experiment with say 2*3*5*7*11=2310, except this time we start from 13, i.e. 13,17,19,23,29,31,37,41,..... 2310+13=2323 2310+17=2327 2310+19=2329 2310+23=2333 2310+29=2339 2310+31=2341 2310+37=2347 2310+41=2351 In this instance we have 2333, 2339, 2341, 2347, and 2353 being prime (notice again that there are no other primes in between these numbers that we missed). Obviously this method gets worse the higher you go up, which is why I want to use Pari (or some other program) to tell me just how much worse this procedure gets the higher you go up. I'm aware that there are probably better ways of finding BIG primes than this, however what I value about this method, is the fact that all the primes generated, are in sequence (that is, even though this method will probably generate many composites, it wont miss/jump over any prime numbers either). Anyway, I figure as long as this method can work adequately well for picking out say 500 digit primes, then I'll use it to tabulate a list of the sequence of primes in this range. Anyway, do you know if Pari can be used somehow to test the accuracy of such a method, and if not, do you know of a program that can? Also since I am still new to this, I don't suppose you can help me with the commands I might have to use if I can use Pari for this? Thanks again. Date: 08/11/2007 at 00:29:13 From: Doctor Vogler Subject: Re: arithmetic progression problem As James wrote to Dr. Math >I tried using that "fordiv" function by typing in something like >(100,X,seq) but I got a message saying something like "expected >character". Try fordiv(100,x,print(x)) >Also I have another short little question for you that I've been >having trouble answering. Suppose I have a composite number N. Is >there sufficient method (other than just trial and error) I can use >that will enable me to find a number 'b' such that when I divide N >by 'b', I get a number that is divisible by 'b+1'. In other words, given N, you want to find some b such that b*(b+1) divides N. Is that what you want? Or do you mean that b doesn't have to divide N, but if you divide N/b and round down, then the quotient is divisible by b+1? If the first, the easiest way is probably to factor N and then try all of the factors. In many cases, there will be no such b. I don't know if there is a way to determine whether there is any such b without factoring N. I rather suspect not. >For example, consider the number 2020. In this instance the only >number that seems to work is when b=42, since 2020-42/43=46. Of >course the only way I could figure this out was by mainly by trial >and error (subtracting even numbers from 2020 and seeing if it is >divisible by a number 1 greater than the number I subtracted). Oh! You mean *subtract* b from N and get (N-b) divisible by b+1. Alternately, if we let m=b+1, then you want to find a number m such that N - (m-1) is divisible by m, or N = -1 (mod m). Again, I would say that the way to answer this question is to factor N+1. Then every factor of N+1 will work as an m, and you can subtract 1 from each m to get a b. >Here's a bit of incentive. If you can tell me of a quick way to do >this, then I can give you a quick way to factor even the hardest and >biggest composite numbers into their primes. This is usually a good way to tell if there isn't any easy way to solve a problem: reduce it to integer factorization. >... >Anyway, I figure as long as this method can work adequately well for >picking out say 500 digit primes, then I'll use it to tabulate a >list of the sequence of primes in this range. > >Anyway, do you know if Pari can be used somehow to test the accuracy >of such a method, and if not, do you know of a program that can. >Also since I am still new to this, I don't suppose you can help me >with the commands I might have to use if I can use Pari for this? It's not clear to me what you're trying to do, but if you're trying to decide which numbers are prime, that's a lot easier to do than factoring the number. In Pari, you can use the "isprime" command. But if you want to know what other commands Pari has, enter a question mark: ? and then try the different sections, especially ?4 and also look in the manual available from the Pari web page. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/