Problem Using Fermat's Little Theorem - Uni Level!

Hey,

I've been working through this linear algebra question about Euclid's Algorithm, Bezaut's Lemma, Chinese Remainder Theorem et al, but seem to have come to a mental impasse about the last part of it where I need to use Fermat's Little Theorem to calculate something...could someone show what I'm supposed to do next to calculate the value in part e) ?

I've scanned in my work to the previous sections as well, so you can understand what I've done thus far.

Rep as always is on offer for helpful souls who can help me understand this more fully. :smile:

Q1. part 1 - resized.jpg108.7KB

Q1. part 2 - resized.jpg83.2KB

Reply 1

ukgea

Note that you can actually use the inverse, as long as the inverse exists, which is the case here because GCD(45, 13) = 0:

45^{35} = 45^{36} \cdot 45^{-1}

This way using inverses for calculation works because

45^{35} = 45^{35} \cdot 1 = 45^{35} \cdot (45 \cdot 45^{-1}) =

= (45^{35} \cdot 45) \cdot 45^{-1} = 45^{36} \cdot 45^{-1}

Hope it helps!

Reply 2

Angel Interceptor

So I could just say that from section b), we know that:

45^-1 modulo 13 = -2 modulo 13 = 11 modulo 13

which would be the answer, right?

Does that methodology make sense?

Reply 3

ukgea

Angel Interceptor

So I could just say that from section b), we know that:

45^-1 modulo 13 = -2 modulo 13 = 11 modulo 13

which would be the answer, right?

Does that methodology make sense?

Yes exactly. In general you can work with stuff raised to negative powers just as you do with positive powers, and it always comes out right, provided that in every step you take you first assert that the inverse in question exists.

But otherwise it's fine.

Related discussions

Latest

Trending

Articles for you

How to get your personal statement sorted fast

Try out the app

Continue on web