Solving modular equivalence problems

[flouran]

Hi Guys,
I am a new user and I was wondering if it is possible to solve the equation, (2x)mod(x+1) = 9, then can't I find x?
Can't I find x by saying that,
Equivalently, http://www.physicsforums.com/latex_i.../2001629-1.png.

Thus, can't I solve for x from there?

P.S. x=10

[alpertron]

2x mod (x+1) = 9
2x = 9 + k(x+1) where k,x integer numbers.

2x - 9 - kx - k = 0

Solving that diophantine equation using my applet you get the four solutions:

(x=-2, k=13), (x=0, k=-9), (x=10, k=1), (x=-12, k=3)

The first two solutions are not solutions of the original congruence because x must be greater than 9.

Plugging in the third solution (x=10):

2(10) mod (10+1) = 20 mod 11 = 9 ok

Plugging in the fourth solution (x=-12):

2(-12) mod (-12+1) = -24 mod -11 = -24 mod 11 = 9 ok.

[flouran]

The link you gave me for your applet was wrong. You initially gave me, http://www,alpertron.com.ar/QUAD.HTM

I believe the correct link is: http://www.alpertron.com.ar/QUAD.HTM; I'm not sure, correct me if I'm wrong.

[flouran]

Quick Question: Say I have (x!)mod(x+3) = 3, how would I use the Diophatine definition of the modular function to solve for x? My approach would be, 3 + k(x+3) = x!, and therefore, 3+kx+3k - x! = 0. Similarly, I could use the Gamma definition of the factorial function to say,


Then how would I solve for x from there?

P.S. At least one of the answers for x should be 4.

[alpertron]

Returning to the math question:

(x!-3) mod (x+3) = 0 (1)

Let x > 3.

If x+3 is composite: x+3 = m*n where m<x and n<x. if m is equal to 3, exchange variables m and n.
x! is multiple of m so x!-3 is not multiple of m (the remainder is m-3), which means that (1) does not hold.

If x+3=p is prime: from Wilson's theorem (p-1)! = -1 (mod p),

x!-3 = (p-1)!/(p-1)/(p-2)-3 = -1/2-3 (mod p)

-1/2-3 = 0 (mod p) -> -1 = 6 (mod p) -> p must be 7 -> x must be 4.