Prime Factors, Modular Arithmetic, and Using Pari

Date: 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/