We need the smallest nonnegative (and integer) `x .`

To find `(a^b) mod c ` we can use two facts that allow as to reduce both `a ` and `b .`

First, `(a^b) mod c = ((a mod c)^b mod c), ` which follows immediately from `(xy) "mod" c = ((x mod c)*(y mod c)) "mod" c.`

The second, less simple fact is that if `gcd(a,c)=1 ` then `( a^b ) mod c = ( a^( b mod phi ( c ) ) ) mod c , ` where `phi ` is Euler's function. This is Euler's theorem.

It is simple to count that `fi(10) = 4 ` and `gcd ( 7 , 10 ) = 1 .`

Thus, `7^( 2017^5778 ) mod 10 = 7^(( 2017^5778 mod 4 )) mod 10` using fact two.

The expression at the top is `( 2017 mod 4 )^5778 mod 4 = 1^5778 mod 4 = 1 ` using fact one.

Combining, we obtain that

`7^( 2017^5778 ) mod 10 = 7 mod 10 = 7 , `

so the smallest `x ` is **3** (7 + 3 = 10).

## See eNotes Ad-Free

Start your **48-hour free trial** to get access to more than 30,000 additional guides and more than 350,000 Homework Help questions answered by our experts.

Already a member? Log in here.

**Further Reading**