Hello and welcome to maths with Jay
Here, we're going to see how we can use Fermat's Little theorem to find the least
residue of a really big number. Another way of thinking about what we're doing here
is that we're finding the remainder when we divide an enormous number by a prime
number. We're going to look at three examples: the first one will be looking
at a relatively small number just so that you can check that we have got the
right answer on your calculator but usually you'd be applying this method to
numbers so big that they just wouldn't fit on your calculator so let's have a look
at the theorem to start with: if we've got an integer "a" and we raise it to a power and
that power is related to the prime number "p" so the power is "p-1"
then we know Fermat's Little theorem tells us that that number is congruent to 1 and here we're working in modulo p
so another way of looking at what this is saying is that when we divide a to the power of p
minus one by p we get a remainder of one. Now this works for any prime number
p and any integer a so long as it isn't divisible by the prime number p. So what
we're going to do is we're going to start with a number as I said that would
fit on your calculator so that you can check the answer, so we're going to start
with 2 to the power of 16 so we're going to find the remainder when it's divided by
17, now if we just look at Fermat's Little Theorem over here, well our a is 2, and I
said we're going to be dividing by seventeen or we're looking at modulo 17, mod 17,
so our p is 17 so 2 to the power 17-1 is going to be congruent to 1,
so all I'm doing here is substituting a as 2 and p as 17 and two isn't divisible by
seventeen so no problem there,
the theorem is going to work, now 2 to the power of 17-1
well that is 2 to the power 16 so what we're being told here is that 2 to the power
16 is congruent to 1 mod 17 so what we've found here, is that if we divide 2 to the
power of 16 by seventeen then we get the remainder of one so let's just see how
we can check this on a calculator: well we could work out what 2 to the power of 16
is, so our calculator checking this 2 to the power 16, our calculator tells us that that's
65536 so we don't actually need to know what that is as an actual number, but it
just helps I think to check what we're doing, and what we're going to do is divide
that number by 17, and that will give us 3855 and a seventeenth.
Now remember we were talking about what the remainder was when we divide by 17 so in fact the
number here, this 3855, well that's really irrelevant, that's got nothing to do with
the remainder, the remainder is this number here, so we have found that we've got the
right answer and the remainder is 1. So 2 to the power o 16 divided by 17 has a remainder of one
Another way of putting this is that the least residue of 2 to the power of 16 in
modulo 17 is one, and what we're going to do next is look at another power of 2, and this time it will be so big that you won't be able to get the
number up on your calculator, or at least its got I think 15, 16
digits so your calculator would give you the number in
standard form so you wouldn't then be able to go on and do a division and check what
the remainder is, not on the calculator I've got anyway, so let's just make a note of what 2 to the
power of 16 is mod 17 because that's going to help us. So we're still going to be working with
two as our base number and working with mod 17 so this time we're going to be looking at
2 to the power of 50
so we want to know what the remainder is going to be when we divide 2 to the power 50
by seventeen, or another way of thinking about this is what the least residue is
in modulo 17, now we going to be able to use what we've already done, we know that 2 to
the power of 16 is congruent to 1, what we need to do is we need to write fifty
in terms of 16 so let's have a look at this, what we're really doing is
dividing 16 into 50 well it goes into 48 that's gonna be sixteen times 3 and 2 left, so
what we can do is say 2 to the power 50 is the same as 2 to the power of, and all we're doing
here is rewriting our index, rewriting the index 50 as 16 times 3 plus 2, then using our
laws of indices you can say, well 2 to the power of sixteen times 3 is the same
as to 2 to the power 16 to the power 3, now we've done that's because we know 2 to the power
of 16 can be replaced by one, now we'll do that in a moment, but let's just finish this off so
we also need to take account of the plus 2 in the index, so that's 2 to the power of 2, so that's just
using out ordinary rules of indices And now, using Fermat's Little theorem, well we know 2 to the power of 16 is congruent to one, so
we can replace that one, so that's one cubed, and then 2 squared well we know that's
equal to 4, so that's congruent to... (mod 17)
the same as one and one times four is just 4, so Fermat's Little theorem has enabled us to say that
when we divide 2 to the power of fifty by seventeen we get a remainder of
four or the least residue of 2 to the power of fifty in mod 17 is 4. So that's a reasonably big number, but next: even bigger number: it's
gonna be one that's got more than 300 digits so really really tricky to do any
arithmetic with that, so the number we're going to look at this time is four to the
power of 532, so a
really enormous number, this one has got more than 300 digits, so it would take
forever to write down the number let alone divide it by anything, and what we're going
to do here is work out the remainder when we divide it by 11 so we're working i
modulo 11 this time, we're going to find the least residue of 4 to the power of
five hundred and thirty-two in mod 11, so let's have a look at how we apply Fermat's Little theorem, so a
this time is going to be four, our prime number is 11, so four to the power of 11-1
is congruent to 1 mod 11, and of course we can then write this as 4 to the power 10 congruent to 1,
so what we need to do here is we need to write four to the power of five hundred
and thirty two as four to the power of 10 times something or other
plus something or other so let's just write down over here what we're doing
five hundred and thirty-two...ten times... so we're dividing 10 into 532 so that
goes in 53 times, that gives us five hundred and thirty so 2 more, so that's
going to give us 53 here plus 2, so it's just ordinary arithmetic on the five
hundred and thirty-two, then using our rules of indices, this is going to be 4 to the power of 10
to the power of 53, times four squared, ok, and then, this is where we're going to use our factored
4 to the power of ten is congruent to 1, this is where we're using Fermat's Little theorem
so this time we're using our congruent symbol in here and that's going to be one
to the power 53 and then we might as well write down what four squared is; it's going to be
16 mod 11, and then we can say that one to the power of anything is one, and 16 is
going to be mod 11, 5, so we now know
that when we divide 4 to the power of five hundred and thirty-two by
11 we get a remainder of 5, or the least residue of 4 to the power of five hundred
and thirty-two in mod
11 is five