From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: a^2+b^2+1=a, mod 2^32? Date: 13 Dec 1994 06:48:15 GMT In article <3ci3pj$jb1@narnia.ccs.neu.edu>, Peter Sherwood wrote: >I'm seeking a proof or counterexample for the following, where all >arithmetic is done modulo 2^32 > >Conjecture: a^2 + b^2 + 1 = a > > has no solution for -(2^32) <= a,b < 2^32, where the > operations of multiplication and addition are performed > using twos' complement computer arithmetic with a 32-bit > word. > Unless I don't understand the architecture restrictions, there is a solution, and in fact it's pretty standard modular arithmetic. Begin with a solution mod 2^n for some small n, then try to get a solution mod 2^(n+1) by choosing a to be one of the two inverse images in the new ring of the value you had in the old ring (likewise for b). In essence, you're computing in the inverse limit of Z/2^nZ. We will find integers a_n (and take b = 1) so that for each n, a_n^2+b^2+1 = a_n mod 2^n. Begin with n=1 and a_1=1. Then if you get as far as a_n, define a_{n+1} = a_n + (a_n^2+2-a_n mod 2^{n+1}). Note that the correction term is either 0 or 2^n by the inductive assumption. In particular, a_{n+1}^2=a_n^2 mod 2^{n+1} by the binomial theorem, for n >=1. On the other hand, the definition of a_{n+1} makes it clear that a_{n+1} = a_n^2+2 mod 2^{n+1}. So we have a_{n+1}^2+b^2+1 = a_{n+1} mod 2^{n+1}, and the induction goes through. For n = 1, 2, ..., I get a_n=1, 3, 11, ..., 1313628251, 3461111899, ... Taking the last two values for a and, again, b=1, gives a^2+b^2+1=a mod 2^31 and 2^32 respectively. I think, however, that your posted conjecture is not what you wanted; shouldn't you be asking for a and b to be at most 2^31 in magnitude if you want 32-bit _signed_ integers? Even if so, I can accomodate you. Given a positive integer a < 2^31 with a^2+(1)^2+1=a mod 2^31 but not mod 2^32, we clearly have a^2+(1+2^30)^2 + 1 = a mod 2^32 with this same value of a. The final interpretation is that you want solutions mod 2^32 which also have a and b bounded in magnitude by 2^16 (so that a^2 and b^2 can be computed without overflow). In that case I haven't a solution but, heck, what's 4 billion or so cases? You can search for solutions with brute force. Hint: Don't use a Pentium :-) dave ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: a^2+b^2+1=a, mod 2^32? Date: 13 Dec 1994 07:47:31 GMT In article <3ci3pj$jb1@narnia.ccs.neu.edu>, Peter Sherwood wrote: >I'm seeking a proof or counterexample for the following, where all >arithmetic is done modulo 2^32 > >Conjecture: a^2 + b^2 + 1 = a > > has no solution for -(2^32) <= a,b < 2^32, where the > operations of multiplication and addition are performed > using twos' complement computer arithmetic with a 32-bit > word. Take a=64878, b=9267. In article <3cjg3f$b7p@mp.cs.niu.edu>, I wrote >but, heck, what's 4 billion or so cases? You can search for solutions >with brute force. Hint: Don't use a Pentium :-) I won't claim I did it so ridiculously. Note a^2-a is even for any a, so b must be odd. On the other hand, a^2-a = c^2-c means (a-c)(a+c-1)=0, even modulo 2^n. If a and c have the same parity, a=c; if not, a=1-c. Thus for any b, one can solve a^2+b^2+1=a mod 2^n using the procedure outlined in the previous post, starting with a=1 (mod 2); the only other solution for a (for this b) is 1-a. Thus I tried all odd b of magnitude less than 2^17 (just for good measure) and solved for a, testing to see if either a or 1-a was less than 2^17 in magnitude. The only other solution was a bit too large for the original problem: b= 9541, a= 92190. (And of course a=-92189) dave (PS - multiplying by 4, we see the original problem is equivalent to solving X^2+Y^2 = -3 mod 2^34) ============================================================================== From: cet1@cus.cam.ac.uk (Chris Thompson) Newsgroups: sci.math Subject: Re: a^2+b^2+1=a, mod 2^32? Date: 13 Dec 1994 22:46:10 GMT In article <3ci3pj$jb1@narnia.ccs.neu.edu>, Peter Sherwood wrote: |> I'm seeking a proof or counterexample for the following, where all |> arithmetic is done modulo 2^32 |> |> Conjecture: a^2 + b^2 + 1 = a |> |> has no solution for -(2^32) <= a,b < 2^32, where the |> operations of multiplication and addition are performed |> using twos' complement computer arithmetic with a 32-bit |> word. It has been suggested that the limits in a and b were meant to be -2^16..2^16, which certainly makes a more interesting problem. One can ask what the minimum value of max(|a|,|b|) is. In article <3cjjij$cal@mp.cs.niu.edu>, rusin@washington.math.niu.edu (Dave Rusin) writes: |> Take a=64878, b=9267. |> |> In article <3cjg3f$b7p@mp.cs.niu.edu>, I wrote |> >but, heck, what's 4 billion or so cases? You can search for solutions |> >with brute force. Hint: Don't use a Pentium :-) |> |> I won't claim I did it so ridiculously. Note a^2-a is even for any a, |> so b must be odd. On the other hand, a^2-a = c^2-c means |> (a-c)(a+c-1)=0, even modulo 2^n. If a and c have the same parity, |> a=c; if not, a=1-c. Thus for any b, one can solve a^2+b^2+1=a mod |> 2^n using the procedure outlined in the previous post, starting with |> a=1 (mod 2); the only other solution for a (for this b) is 1-a. |> Thus I tried all odd b of magnitude less than 2^17 (just for good |> measure) and solved for a, testing to see if either a or 1-a |> was less than 2^17 in magnitude. The only other solution was a bit too |> large for the original problem: b= 9541, a= 92190. (And of course |> a=-92189) |> |> dave |> |> (PS - multiplying by 4, we see the original problem is equivalent to |> solving X^2+Y^2 = -3 mod 2^34) Indeed so, and that gives a way of finding the above solutions without an order sqrt(2^32) search (although as it involves factorising numbers it may not really be faster for such a small number as 2^32). We look for solutions of a^2 + b^2 + 1 = n * 2^32 + a or (2a-1)^2 + (2b)^2 = n * 2^34 - 3 for n=1,2,... We find that 2^34-3 = 5113 * 3360037 = (53^2+48^2) * (1519^2+1026^2) = 129755^2 + 18354^2 = 31259^2 + 127290^2 giving the solutions a = 64878 or -64877, b = +-9267 a = 15630 or -15629, b = +-63645 [*] Trying n=2 we have 2^35-3 = 5.prime = (2^2+1^2) * (77568^2+29243^2) = 184379^2 + 19082^2 = 125893^2 + 136054^2 and solutions a = 92190 or -92189, b = +-9541 a = 62947 or -62946, b = +-68027 n=3 and n=4 give no solutions because 2^34*n-3 has prime factors =3 mod 4. This is enough to show, for example, that the solution marked [*] above is the one with smallest max(|a|,|b|). Once you have the prime factorisations, finding the expressions as the sums of squares can be done by Cornacchia's algorithm (indeed, I did), and is polynomial in the size (i.e. logarithm) of the numbers involved. There is another possible interpretation of the original question, though. Suppose that comma in "-(2^32) <= a,b < 2^32" was meant to be a dot, and we are being asked to minimise the product |ab|. I don't see any better way of doing that taking L = sqrt(|ab|) for a known good solution as above and following Dave Rusin's line, solving for b for all |a| <= L and for a for all |b| <= L. Chris Thompson Internet: cet1@phx.cam.ac.uk JANET: cet1@uk.ac.cam.phx ============================================================================== From: jomcgow@eis.calstate.edu (John S. McGowan) Newsgroups: sci.math Subject: Re: a^2+b^2+1=a, mod 2^32? Date: 13 Dec 1994 12:07:26 -0800 roth@wrksys.enet.dec.com (Jim Roth) writes: > > In article <3ci3pj$jb1@narnia.ccs.neu.edu>, gbcacm@ccs.neu.edu (Peter Sherwood) writes... > >I'm seeking a proof or counterexample for the following, where all > > >Conjecture: a^2 + b^2 + 1 = a > > > > has no solution for -(2^32) <= a,b < 2^32, where the > Actually, a brief experiment seems to show that the congruence > a^2 + b^2 + 1 = a mod n has n solutions for n a power of 2, and > 0 solutions for n a multiple of 9, for 0 <= a, b < n. > > Amusing. Proof? > For n a multiple of 9, complete the square to convert the question to: x^2+y^2=-3 mod 4n or with 4n=9k, does there exist an N so that 9kN-3=3(3kN-1) can be written as the sum of two squares? But it has exactly one factor of three and a number can be written as the sum of two squares iff every prime of the form 3+4j which divides it occurs to an even power. So... no solutions for n divisible by 9. Regards, -- John S. McGowan | jmcgowan@bigcat.missouri.edu [COIN] (preferred) | j.mcgowan15@genie.geis.com [GEnie] ---------------------------------------------------------------------- ============================================================================== From: jomcgow@eis.calstate.edu (John S. McGowan) Newsgroups: sci.math Subject: Re: a^2+b^2+1=a, mod 2^32? Date: 13 Dec 1994 11:59:03 -0800 gbcacm@ccs.neu.edu (Peter Sherwood) writes: > I'm seeking a proof or counterexample for the following, where all > > Conjecture: a^2 + b^2 + 1 = a > > has no solution for -(2^32) <= a,b < 2^32, where the RE: Does there exist a solution to: a^2+b^2+1=a mod 2^r? (ANSWER: Yes. For any r.) I see someone posted a solution... but, in case anyone is interested here is a proof that a solution exists for each r. Lemma: For any s there exists an integer M so that M*2^s-3 can be written as the sum of two squares. Proof: (Induction) 2^5-3=29=2^2+5^2=2*2^4-3=4*2^3-4=8*2^2-3=16*2^1-3 so that we have the result for s=1,2,3,4,5 (in particular for s=3). Suppose we know that there exists an M with M*2^s-3 decomposable into a sum of two squares for some s(>2). If M is even, then one can decompose (as a sum of two squares) M*2^s-3=(M/2)*2^(s+1)-3 and we have s+1. If M is odd, let A=2^(s-1)+1 so that A^2=2^(2s-2)+2^s+1=[2^(s-2)+1]*2^s+1=N*2^s+1 where N is odd (since s>2). As M*2^s-3 can be written as a sum of two squares, so can A^2*(M*2^s-3) (as we are just mutliplying by a square) which equals (N*2^s+1)(M*2^s-3)=MN*2^(2s)+(M-3N)*2^s-3 but M and N are odd, so M-3N has a factor of two and this is J*2^(s+1)-1 where J=MN*2^(s-1)+[(M-3N)/2]. Q.E.D. Completing the square in a^2+b^2+1=a mod 2^r yields an equivalent equation: x^2 + y^2 = -3 mod 2^(r+2) where x=2a-1 and y=2b, so that the original question is equivalent to: Do there exist M, x and y so that M*2^s-3=x^2+y^2 where s=r+2? That is, does there exist an M so that M*2^s-3 [s=r+2] can be written as the sum of two squares? As this can be done for any s=r+2, there is a solution to the equation for any r. Regards, John S. McGowan | jmcgowan@bigcat.missouri.edu [COIN] (preferred) | j.mcgowan15@genie.geis.com [GEnie] ---------------------------------------------------------------------- ============================================================================== From: cet1@cus.cam.ac.uk (Chris Thompson) Newsgroups: sci.math Subject: Re: a^2+b^2+1=a, mod 2^32? Date: 16 Dec 1994 15:08:48 GMT In article <3cl87i$2bi@lyra.csx.cam.ac.uk>, I wrote: |> |> There is another possible interpretation of the original question, though. Suppose |> that comma in "-(2^32) <= a,b < 2^32" was meant to be a dot, and we are being |> asked to minimise the product |ab|. I don't see any better way of doing that |> taking L = sqrt(|ab|) for a known good solution as above and following Dave Rusin's |> line, solving for b for all |a| <= L and for a for all |b| <= L. In the unlikely event of anyone wanting to know the answer to this version, the minimum |ab| is achieved by a=-69, b=+-3893743, and the following are the solutions with |ab| < 10^9: a |b| |ab| a |b| |ab| -69 3893743 268668267 70 3893743 272562010 -301 924499 278274199 302 924499 279198698 -64877 9267 601215159 64878 9267 601224426 -90 8392703 755343270 91 8392703 763735973 -833855397 1 833855397 833855398 1 833855398 -92189 9541 879575249 92190 9541 879584790 -2 479772853 959545706 -15629 63645 994707705 15630 63645 994771350 Chris Thompson Internet: cet1@phx.cam.ac.uk JANET: cet1@uk.ac.cam.phx