4248.sagews

1.

mod(2^-1,67862310031)

33931155016

3.

mod(122^-1,343)

194

3(b)

(2^27-1)X=7^3mod(2^22-1)

can be split as product of two congruences,

(2^27-1)X=1mod(2^22-1)

1=7^3mod(2^22-1)

For Solvingfirst congruence,

(2^27-1)X=1mod(2^22-1)

or X=(2^27-1)^-1mod(2^22-1)

we first find inverse of 2^27-1

mod((2^27-1)^-1,2^22-1)

1353001

Thus X=7^3*((2^27-1)^-1) Mod (2^22-1)

or X=1353001*7^3 mod(2^22-1)

mod(1353001*7^3,2^22-1)

2706013

3(c)

mod(193707721^-1,761838257287)

119801956159

4(a)

a = 765355768, b = 76354890023, c = 863429

a = 765355768;
b = 76354890023;
c = 863429;
GCD_1=xgcd(a,b);
X_0= GCD_1[1]*c/gcd(a,b);
X=X_0
k=1;
while X<=0 :
 X=X_0+b*k/gcd(a,b)
 k=k+1;
print X

39334375343

a = 765355768;
b = 76354890023;
c = 863429;
xgcd(a,b)

(1, -11358092426, 113849703)

4(b)

a = 2^100-1;
b = 2^102-1;
c = 6442450941;
GCD_1=xgcd(a,b);
X_0= GCD_1[1]*c/gcd(a,b);
X=X_0
k=1;
while X<=0 :
 X=X_0+b*k/gcd(a,b)
 k=k+1;
print X

1690200800304305868653681005913

4(c)

a = 3014774729910783238001;
b = 15733624667337520130581;
GCD_1=xgcd(a,b);

a = 3014774729910783238001;
b = 15733624667337520130581;


GCD_1=xgcd(a,b);
X_0= GCD_1[1]*c/gcd(a,b);
X=X_0
k=1;
while X<=0 :
 X=X_0+b*k/gcd(a,b)
 k=k+1;
print X

41811455202773941761/950017208401

a = 3014774729910783238001;
b = 15733624667337520130581;


xgcd(a,b);

(950017208401, 6489992021, -1243570020)

7.

41*41*40
mod(72549625,67240)
mod(3^64905,41^3)
101^2*100
mod(72549625,1020100)
251*250
mod(72549625,62750)
mod(3^122525,101^3)
mod(3^10625,251^2)
CRT_list([12549,796294,25854],[41^3,101^3,251^2])

3994608808930448

8.

euler_phi(1000)

400