A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a-by-b rectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b. So the task is to find the largest square that tiles the rectangle completely. See below:
Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.
So the example compiled down to arithmetic steps would be as follows:
Thus 21 is the GCD of 1071 & 462
A code is implemented with the following statement. Decrypt the code.
The totient of 3131 is needed and is found below:
because 31 and 101 are prime
Eulers Theorem: so:
Where m is an integer to give us more flexibility in generating an inverse in step XXX below. Multiply both sides by x
So if you can find a power d where:
then you can take the encrypted numbers to the power of d and out will pop the plain text original series
Now you use the Euclidean algorithm to find 1 in terms of 197 and 3000. This yields:
Taking the mod(3000) of both sides
which shows is the decryption power we are looking for
This example used smaller numbers so as to make the example transparent. However if the input character were to be X=31 or 101 I think the system breaks down.
A farmer has 100 dollars to buy 100 animals. A cow costs 10, a pig costs 5 and a chicken costs 50 cents. How many of each does he buy? He must use all his money and he must buy at least 1 of each type.
note Z must be even because otherwise you will get ddd.5<> 100 in the first equation. Eliminate z by multiplying first equation by 2 and subtracting the second equation
Here a solution is only found because the solution is specified to be integers
Brute force Integer solution
Find a solution for the above and plugging into: now plug in number until you get an even z. Try x=1:
and is even and thus the problem is done
Two obvious solutions are
The first solution is viable. The second is not because there is no money left over to buy any other type of animal.