Finding Modulus Relations in Equations

[TylerH]

Where, on the internet, can one learn the method to solving equations modulus a number? I'd like to learn the method for finding such relations as this special case for the Erdos-Straus Conjecture, with n ≡ 2 (mod 3).

Also, what is the technical name for finding the mod n relations in an equation?

 

[Sandor]

I'm pretty sure that you solve it in relatively the normal way. Normally, you end up with a rational number solution to a linear system. Well, over integers, modulo some number, the number in the denominator is not actually divided by in the usual way, but let's say the denominator is d, then you would find the integer q such that d*q=1 mod (whatever), and instead of dividing by d as you would in a linear system over the real numbers, over the integers modulo whatever, you would then multiply by q. The one thing to watch out for, is that if d and whatever (I should have given it a variable letter darnit) have a common factor, if they aren't relatively prime, then there will be no solution for q. But that's nothing new, that's just a new way for the determinant to be 0. So if the determinant of the matrix describing your linear relation is not just 0 as it is with linear systems over all real numbers, but any integer which has any factor in common with "whatever", then you can't solve it.

Now, if you want to solve it where each line in the linear system is modulo a different number, for instance x+3y=4 mod 5, and 2x-y=2 mod 6, then that method isn't going to work. And if it is a nonlinear equation, that is NP complete, so you'd best avoid trying unless you have a polynomial time algorithm for NP problems.

 

[robert Ihnot]

The reference given, as you know, completely handles the case for n==2Mod3. This comes about from the form, where( n-2)/3 is an integer. It seems possible that the form was just found by chance. $$\frac{4}{n} =\frac{1}{n} +\frac{1}{(n-2)/3+1}+\frac{1}{(n^2+n)/3}$$

Which, but not in the right form, simplifies to: $$\frac{4}{n}=\frac{1}{n}+\frac{3}{n+1}+\frac{3}{n^2+2}$$

This is a more complex form harder to find than a simpler form, which may have been a starting point for the above, $$\frac{2}{n} = \frac{1}{n}+\frac{1}{n+1}+\frac{1}{n^2+n}$$

This uses a splitting method and if length is not a problem, we could replace 1/(n+1) with 1/(n+2) + 1/(n+2)(n+3) Thus the length of the Egyptian fraction could be increased and increased, but in the case under consideration we are only interested in three term Egyptian fractions.

Maybe you want to study Egyptian fractions further, I am not exactly sure of your questions. The standard method on solving multiple congruences is the Chinese Remainder Theorem.

Now on that simple form above we can find things like 1/5=1/10+1/11+1/110. So that 2/p can always be found in three terms of an Egyptian fraction.

However, in the specialized case of 4/n dealing with 3 Egyptian fractions, Mordel has shown that certain forms will not work like the case of n==2 Mod 3. In fact, Mordel shows that n==1 Mod 3 will not work the same way so we can not rely on a similar polynominal identity for all cases.

 

[robert Ihnot]

$$\frac{4}{n}=\frac{1}{n}+\frac{3}{n+1}+\frac{3}{n^2 +2}$$

The above was a mistake, and should be: $$\frac{4}{n}=\frac{1}{n}+\frac{3}{n+1}+\frac{3}{n^2 +n}$$

Here is my improvised form: $$\frac{4}{n} = \frac{1}{n/3}+\frac{1}{n+1}+\frac{1}{n^2+n}$$

Which will work as long as 3 divides n, for example= 4/15=1/5+1/16+1/240.

Now the only thing we would need to compete the problem would be to solve for n==1Mod 3, which Mordel assures us is not possible. However with a minus sign, we would have: $$\frac{4}{n} = \frac{1}{n} +\frac{1}{(n-1)/3}-\frac{1}{(n^2-n)/3}$$