How do I calculate 40^77 mod 119?
Solving mod is very tricky, yet very simple if you understand the mod and its function.I am solving a small example so that the procedure is understood.Let's find 45^5 mod 31We can write 45^5 = (45^2)*(45^2)*45Therefore, 45^5 mod 31 = ((45^2 mod 31)*(45^2 mod 31)*45) mod 31Which equals (10*10*45) mod 31Which is 5.I will solve this question in two ways. Hope you get the jist.1. In the power ot 2s :We have, 40^77mod119= ((40^2)^38)*40 mod 119= (((40^2 mod 119)^38 mod 119 * 40) mod 119= (((53^38) mod 119) * 40) mod 119= (((53^2 mod 119) ^19 mod 119 * 40) mod 119= ((72^19 mod 119 * 40) mod 119= (((72^2 mod 119)^9)mod 119 *40*72) mod 119= ((67^9 mod 119) * (40*72) mod 119))mod 119= (((67^2 mod 119)^5)mod 119 * (24*67)mod 119) mod 119= (86^4 mod 119 * 61) mod 119= 86*24 mod 119= 102. In the power of 3s:We have, 40^77mod119= (((40^3)^25)*(40^2)) mod 119= (((40^3 mod 119)^25 mod 119 * (40^2 mod 119) mod 119= (((97^25) mod 119) * 53) mod 119= (((97^3 mod 119) ^8 mod 119 * (53*97)mod 119) mod 119= ((62^8 mod 119 * 24) mod 119= (((62^3 mod 119)^2)mod 119 *( 24*62*62) ) mod 119= ((90^2 mod 119) * (24*62*62) mod 119))mod 119= (8 * 31) mod 119= 10 Thus the final answer is 10.
How do I solve the linear diophantine equation [math]3x + 6y +5z = 7[/math]?
Consider the equation[math]\begin{align}\displaystyle 3x+6y+5z-7=0\end{align}\tag*{}[/math]In 3D space, this represents a plane with normal vector [math]\widehat{v}(3,6,5)[/math]. Bearing this in mind, here’s what we are going to do:Find a point on the plane with integer coordinatesFind two non-parallel vectors with integer components that lie on the planeExpress any other point on the plane with integer coordinates as a linear combination of these two vectors applied to our starting pointStep 1Trying some values for [math]x[/math], [math]y[/math] and [math]z[/math] we quickly find the point [math]P(-1,0,2)[/math] that lies in the plane and has integer coordinates.Step 2The vector [math]\hat{v}(3,6,5)[/math] is normal to the plane; therefore, any vector parallel to the plane should be perpendicular to [math]\hat{v}[/math]. So, if [math]\widehat{w}[/math] lies in the plane, then [math]\hat{v}\cdot{\hat{w}}=0[/math]. After some attempts (e.g for both vectors [math]\hat{w_a}[/math] and [math]\hat{w_b}[/math] that lie on the plane, set a component to [math]0[/math] and choose the other two components in such a way as to make the scalar products [math]\hat{w_a}\cdot{\hat{v}}[/math] and [math]\hat{w_b}\cdot{\hat{v}}[/math] equal to [math]0[/math]) we quickly come up with [math]\hat{w_a}(5,0,-3)[/math] and [math]\hat{w_b}(0,5,-6)[/math].Step 3Let [math]\hat{u}(-1,0,2)[/math] be the positional vector of the first point we found. Any other point with integer coordinates (i.e its positional vector) can be expressed as[math]\begin{align}\displaystyle \hat{u}+k\cdot{\hat{w_a}}+h\cdot{\hat{w_a}}\end{align}\tag*{}[/math]Hence the solution[math]\begin{align}\displaystyle\begin{cases}x=-1+5k\\y=5h\\z=2-3k-6h\end{cases}\end{align}\tag*{}[/math]with [math]k,h\in{\Z^2}[/math].