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)