- #1

Playdo

- 88

- 0

This method utilizes discrete binary operations, in particular notice that.

(I1) [tex]Div(x+y+z,a)=Div(x,a)+Div(y,a)+Div(z,a)+\{0,1,2\}[/tex]

This means that for one of the elements of the included set {0,1,2} the equation is true. This notation is quite useful for carrying out long calculations using integer division as will be apparent in a moment.

Also note that

(I2) [tex]Div(xy,a) \leq yDiv(x,a) \leq xDiv(y,a) if y>x[/tex]

Now we first start with a type of quadratic template for a natural number N, that is

(1) [tex]N=XY \rightarrow az+t =(ax+s)(ay+r)[/tex]

Notice we do not require N and a coprime. This leads immediately to

(2) [tex]z = axy+ sy+rx + Div(rs,a)[/tex]

This is because [itex]t=Mod(rs,a)[/itex] was removed after expanding the product XY.

Equation 2 can be further dealt with by noting that

(3) [tex]Mod(z,a) = Mod(sy+rx+Div(rs,a),a)[/tex]

(4) [tex]Div(z,a) = xy + Div(sy+rx+Div(rs,a)) = xy + Div(sy)+Div(rx)+Div(Div(rs,a),a) + \{0,1,2\}[/tex]

Equation four can be categorized depeending on the relationships of s to y and r to x. Notice that [itex]Div(Div(rs,a))<Div(a-2,a) = 0[/itex] therefore this term is obliterated. If we restrict x and y to be less than a then [itex] Div(sy,a)<a-2[/itex]. So by dividing (4) by a again we obtain

(5) [tex]Div(Div(z,a),a) = Div(xy+Div(sy)+Div(rx)+\{0,1,2\},a)[/tex]

[tex]= Div(xy,a)+Div(Div(sy,a))+Div(Div(rx,a))+Div(\{0,1,2\},a)+\{0,1,2,3\}[/tex]

Or in the sixth step

(6) [tex]Div(Div(z,a),a) = Div(xy,a) + \{0,1,2,3\}[/tex]

Ah the beauty of the seventh step!

(7) [tex]Div(xy,a) = Div(Div(z,a),a)-\{0,1,2,3\}[/tex]

After this we recognize that in short order we know a key ingredient if you will of xy since the division algorithm shows us that

(8) [tex]xy = Div(xy,a)+Mod(xy,a)[/tex]

But of course we know that Mod(xy,a) is greater than zero and less than a, this is not as impressive as we wish it to be. if N and a are coprime we reduce the residues to be searched to the reduced residue system modulo a. But perhaps by taking the modulus of Equation four we can obtain a better estimate.

(9) [tex]Mod(Div(z,a),a) = Mod(xy,a) + Mod(Div(sy+rx+Div(rs,a)),a)[/tex]

[tex]= Mod(xy,a) + Mod(Div(sy),a)+Mod(Div(rx),a)+Mod(\{0,1,2\},a)[/tex]

The modulus of the set {0,1,2} is clearly equal to itself. The modulos of the terms containg sy and rx will be harder to come by. In fact right now I do not see a way past the terms of the form [itex]Mod(Div(sy,a))[/tex].

(I1) [tex]Div(x+y+z,a)=Div(x,a)+Div(y,a)+Div(z,a)+\{0,1,2\}[/tex]

This means that for one of the elements of the included set {0,1,2} the equation is true. This notation is quite useful for carrying out long calculations using integer division as will be apparent in a moment.

Also note that

(I2) [tex]Div(xy,a) \leq yDiv(x,a) \leq xDiv(y,a) if y>x[/tex]

Now we first start with a type of quadratic template for a natural number N, that is

(1) [tex]N=XY \rightarrow az+t =(ax+s)(ay+r)[/tex]

Notice we do not require N and a coprime. This leads immediately to

(2) [tex]z = axy+ sy+rx + Div(rs,a)[/tex]

This is because [itex]t=Mod(rs,a)[/itex] was removed after expanding the product XY.

Equation 2 can be further dealt with by noting that

(3) [tex]Mod(z,a) = Mod(sy+rx+Div(rs,a),a)[/tex]

(4) [tex]Div(z,a) = xy + Div(sy+rx+Div(rs,a)) = xy + Div(sy)+Div(rx)+Div(Div(rs,a),a) + \{0,1,2\}[/tex]

Equation four can be categorized depeending on the relationships of s to y and r to x. Notice that [itex]Div(Div(rs,a))<Div(a-2,a) = 0[/itex] therefore this term is obliterated. If we restrict x and y to be less than a then [itex] Div(sy,a)<a-2[/itex]. So by dividing (4) by a again we obtain

(5) [tex]Div(Div(z,a),a) = Div(xy+Div(sy)+Div(rx)+\{0,1,2\},a)[/tex]

[tex]= Div(xy,a)+Div(Div(sy,a))+Div(Div(rx,a))+Div(\{0,1,2\},a)+\{0,1,2,3\}[/tex]

Or in the sixth step

(6) [tex]Div(Div(z,a),a) = Div(xy,a) + \{0,1,2,3\}[/tex]

Ah the beauty of the seventh step!

(7) [tex]Div(xy,a) = Div(Div(z,a),a)-\{0,1,2,3\}[/tex]

After this we recognize that in short order we know a key ingredient if you will of xy since the division algorithm shows us that

(8) [tex]xy = Div(xy,a)+Mod(xy,a)[/tex]

But of course we know that Mod(xy,a) is greater than zero and less than a, this is not as impressive as we wish it to be. if N and a are coprime we reduce the residues to be searched to the reduced residue system modulo a. But perhaps by taking the modulus of Equation four we can obtain a better estimate.

(9) [tex]Mod(Div(z,a),a) = Mod(xy,a) + Mod(Div(sy+rx+Div(rs,a)),a)[/tex]

[tex]= Mod(xy,a) + Mod(Div(sy),a)+Mod(Div(rx),a)+Mod(\{0,1,2\},a)[/tex]

The modulus of the set {0,1,2} is clearly equal to itself. The modulos of the terms containg sy and rx will be harder to come by. In fact right now I do not see a way past the terms of the form [itex]Mod(Div(sy,a))[/tex].

Last edited: