Solving two-variable equations mod p

asked 2017-09-29 15:13:34 +0200

dcole gravatar image

I am able to, in wolfram alpha, plug in the equation

11=x*(y^119)^149mod151

and wolfram is able to give me a set of non-zero solutions (x,y) that I think satisfy (11*y^119, y)

I have tried using symbolic equations and the sage quickstart for number theory to replicate this functionality, but I am getting stuck on some integer conversion TypeErrors in sage.

I have tried to set it up like:

x,y = var('x,y');

qe=(mod(x*(y^119)^149,151)==mod(11,151))

Can someone help me set up this equation, and then solve for all possible non-zero solutions?

THanks!

edit retag flag offensive close merge delete

Comments

What does it mean solutions (x,y) that [...] satisfy (11y^119, y)* ?

There is no need to "solve", for we can simply isolate $x$ in the equation. Of course, $x,y\ne 0$ in the field $F=\mathbb F_p$ with $p=151$ elements. And for each $y\ne 0$, we can obtain the corresponding $x$. Also, why use the complicated expression $$ (y^{119})^{149} = y^{119\cdot 149}$$ in the field $F$, where $a^p=a$ for all $a\in F$? (Fermat.)

Code for the tuples:

p = 151
F = GF(p)
g = ( 119 * 149 ) % (p-1)

sols = []
for y in F:
    if y == F(0):    continue
    x = F(11) / y^g
    sols.append( (x,y) )

sols = sorted( sols, key=lambda sol: sol[0] )
for sol in sols:
    print "x=%3s y=%3s" % sol

Remove the sorted line if $y$ is the main variable.

dan_fulea gravatar imagedan_fulea ( 2017-09-30 22:10:00 +0200 )edit

The equation is: $$x=11y^{119}\ ?$$

dan_fulea gravatar imagedan_fulea ( 2017-09-30 22:10:40 +0200 )edit
add a comment