2009/001) Find the smallest positive integer x for which 7x^25 - 10 is completely divisible by 83.

We are given
7x^25 = 10 mod 83We should make the coefficient of x^25 as 7
to get rid of 7 multiply by inverse of 7we have GCD(7,83) = 1using extended eulers algorithm 6 = 83- 7 *11 1 = 7- 6 = 7*12 – 83
so inverse of 7 is 12multiply by 12 on both sides knowing 7*12 = 1 mod 83 we get x^25 = 10 * 12 mod 83 = 37
now we need to raise a power so that x^82 = 1 mod 1now we need to find reciprocal of 25 mod 82again using extended eulers algorithm82 = 3*25 + 7
7 = 82 - 3* 2525 = 7*3 + 4 or4= (25-7*3) = (25-3*(82-3*25) = 10 * 25 - 3*82now knowing 1 = 2*4 - 7 = 2(10*25-3*82) - (82-3*25)= 23*25 - 7*82
so reciprocal of 25 is 23so raise the number to the power 23x= 37^23 mod 83= 37* (37*2)^11 mod 83= 37 * (1369)^11 mod 83= 37 * 41^11 mod 83= (37*41)* 41 ^10 mod 83= 23 *41 ^10 mod 83= 23 *(41^2)^5 mod 83= 23 *21^5 mod 83= 23*21 * 21^4 mod 83= 483 * 21^4 mod 83= 68 * 21^4 mod 83= 68 * 441 * 441 mod 83= 69