From: phelix@vallnet.com
Date: Mon, 20 Oct 1997 15:54:40 +0800
To: cypherpunks@Algebra.COM
Subject: Re: A Math problem related to cryptography
Message-ID: <3454d05d.32951635@128.2.84.191>
MIME-Version: 1.0
Content-Type: text/plain



On 19 Oct 1997 18:36:26 -0500, Jeffery Walker <jeff@beol.net> wrote:

>
>	I have been working on some math and C++ code to implement it. The
>problem relates to a possible new means of factoring.  However, I have run
>into a problem which I cannot solve. Indeed it maybe impossible. The
>problem is this:
>
>	Find and equation using only multiplication, division, GCD, LCM and
>powers (not addition or subtraction) in terms of a and b which is equal to
>a+b for all Integers.  If so desired it can be assumed that a and b are
>relative primes with a>b.  Note that equivalent problems include but aren't
>limited to finding a similar equation for a+1. If other functions such as
>logs are required they may be allowed but I would have to look into it.
>
>	To encourage people to answer I am offering $20 for a solution and
>$10 for a proof that it is impossible.  I will judge all answers as to the
>validity both in terms of actually being correct (or in the case of a proof
>a valid argument) and in that they do not use functions such as addition or
>subtraction which are not allowed.
>

(why do I get the feeling that I'm doing somebody's homework assignment)

Claim: In the realm of Integers, There does not exist a formula using only
multplication,division,GCD,LCM,and powers such that f(a,b)=a+b for all
integers a,b

Proof (by contradiction):  

I  assume that a,b are primes > 2.  Lets also define  x,y,z,w,m,n and any
integer >=0 and C,D,E as any integer > 0.  Now let's look at the operations
available to us:

multiplication and powers:
	C=C*(a^0)*(b^0)
	CD=E(a^0)*(b^0) where E=CD
	a=1*(a^1)*(b^0)
	a^2=1(a^2)*(b^0)
	Cab^2=C*(a^1)*(b^2)
	well , all results can be expressed in the following form:
		C*(a^x)*(b*y)

division:
	a !| b and b !| a (here !| means "does not divide")
	(From here on out, lets assume that a !| C,D,E and b !| C,D,E.  it
makes things simpler)
	Ca/a=C*(a^0)*(b*0)
	Ca/D=E*(a^1)*(b^0) assuming that E | C
	I won't go through all this.  It should be obvious that for all
allowed divisions, the result can be expressed as
		 C*(a^x)*(b*y)


GCD:
	gcd(a,b)=1
	
	gcd(a,C)=1
	gcd(Ca,Da)=max(a,gcd(C,D))
	gcd(Ca,Db)=gcd(C,D)
	gcd(C(a^x),C(a^y))=C(a^(min(x,y)))

gcd(C(a^x)*(b^y),D(a^z)*(b^w))=gcd(C,D)*(a^(min(x,y)))*(b^(min(z,w))))
	=E(a^m)*(b^n) for E=gcd(C,D) m=min(x,z) and n=min(y,w)

	so, all results of GCD can be expressed in the form:
		C(a^x)(b^y)

LCM:
	LCM(C,D)=CD/gcd(C,D)
	LCM(C(a^x)*(b^y),D(a^z)*(b^w))
	  =CD*(a^(x+z))*(b^(y+w))/gcd(C(a^x)*(b^y),D(a^z)*(b^w))
	  =( CD/gcd(C,D) * (a^(|x+z-min(xz)|)) * (b^(y+w-min(yw))
	  = E(a^m)*(b^n) where E=CD/gcd(C,D)=lcm(C,D), 
	        m=x+z-min(x,z) , n=y+w-min(y,w)

	so, all results of LCM can be expressed in the form:
		C(a^x)(b^y)

Now, as you can probably tell by now, I don't remember a damn thing about
groups, rings, and fields.  If i did, I could have done all of the above in
one paragraph.  SO, what I'm trying to say is that all the numbers you can
operate on here will be of the form C(a^x)(b^y).  SO you really have to
prove at least the following

	C(a^x)(b^y)=a+b   for some C>0, x,y>=0 integers

Now, you could probably say that C=a+b, x,y=0, but that's a cop out and is
probably not allowed.  Now, watch while I cop out and provide an easy
counterexample:

	assume some formula exists such that f(a,b)=a+b with
	f only using *,/,gcd,lcm,^ operators

	let a=5, b=7
	
	Since I know that ultimately anything I do with constants
	and the operators 8,/,gcd,lcm,^ will result in something in
	the form of C(a^x)(b^y), I won't even mess with the formula

	there must exist some C>0, x,y>=0 that makes:
		C(5^x)(7^y)=5+7=12

	of x>=1 and y>=1 then C(5^x)(7^y)>12 for all C>0
	if x=0 and y=0, C=12  (this works)
	if x=1,y=0 then 5C=12.  there is no C which satisfies this.
	if x=0,y=1 then 7C=12.  there is no C which satisfies this.
	
	so, the only solution is C=12, or more generally, C=a+b

	oops, that can't be the formula since we're not allowed to
	do that. QED.

	Well, that was pretty sloppy, so lets be more general about this:
		C(a^x)(b^y)=a+b
		
	Now, I'm sure that somewhere in the history of mathematics
	somebody has proven that for primes a and b where a,b>2
	that a*b>a+b.

	So, for any x,y,C>0, C(a^x)(b^y)>a+b.

	C, of course, cannot be negative, or zero, so all were left 
	with is x or y being zero. Let y=0.  we have:
	
		C*a^x=a+b
		C*a^x - a = b
		a*(C*a^(x-1) - 1 ) = b
		a*E=b

	Now, a and b are primes and a!=b.  From the fundamental 
	theorem of algebra, every number can be represented by a 
	series of primes such as:
		p1^a1 * p2^a2 * p3^a3 * ...

	In a*E=b, if we factor each side down to its primes, we find that
	the right hand side does not contain the prime 'a' which  is on 
	the left hand side, so a*E != b.  A similar argument can be used 
	for the case x=0.

	This leaves the only solution to C(a^x)(b^y)=a+b being
		x=0,y=0
		C(a^0)(b^0)=C=a+b
	which isn't allowed.  QED



Now, If you're like me, you've probably read the above and don't have a
f*cking clue what I meant (I sure wouldn't if I read all that crap).  So
here's the executive summary.

With the operators you've defined on the number set you want to work with,
no matter how complicated or crazy your formula is, I can express the
result at C(a^x)(b^y).  And hopefully, I've shown that C(a^x)(b^y) cannot
equal a+b except in the trivial case of C=a+b (with x,y=0) which is what
you don't want.

>Thanks,
>Jeff
>P.S. I am very interested in joining the coderpunks list as I do program
>and am interested in cryptography as related to programming.  If someone
>would be kind enough to recommend me I thank you.
>
I wasn't aware that you had to be invited to the coderpunks list.  Just
send a message to majordomo@toad.com with the following in the body:

subscribe coderpunks



-- Phelix, who really should have been able to give a better proof
(especially since one of my degrees has the word 'Mathematics' on it)