Question 1205778: Hi, I have shown my working for the question below, am I on the right track?
〖Simplify 10〗^241 mod(13)
Fermat’s Little Theorem states:
a^(p-1)≡1mod(p)
Substitute:
10^12≡1mod(13)
By our multiplication theorem we know that if
10^12≡1mod(13)
Then
10^((12)A)≡(1)^A mod (13)
We want to get from a power of 12 up to around 241, and 12 x 20 = 240
10^(12)(20) ≡1^20 mod(13)
≡1mod(13)
So what we have so far is
10^241 mod(13)≡10^240×10^1 mod(13)
≡1×10mod(13)
≡10mod(13)
When 10^241is divided by 13, the remainder is 10
Thank you
Found 3 solutions by ikleyn, math_tutor2020, Edwin McCravy:
Answer by ikleyn(52787)   (Show Source):
Answer by math_tutor2020(3817)  (Show Source):
You can put this solution on YOUR website!
You have the correct line of thinking and correct answer. Nice work.
This first section basically restates what you mentioned.
The next two sections will go over other approaches.
Fermat's Little Theorem (FLT)
)
'a' is an integer
p is prime
Special case of FLT
)
where p is not a factor of 'a'
) Due to the special case of FLT
^{20} \equiv 1^{20} (\text{mod } 13)) Raise both sides to the 20th power
) Use the rule that (a^b)^c = a^(b*c)
)
) Multiply both sides by 10
)
) Use the rule that a^b*a^c = a^(b+c)
)
--------------------------------------------------------------------------
A 2nd approach:
Let's look at powers of 10^n (mod 13) to see if we can spot any patterns.
)
) because 100/13 = 7 remainder 9. We only care about the remainder.
) because 90/13 = 6 remainder 12.
) because 120/13 = 9 remainder 3
You can keep this process going.
I'll use a spreadsheet to extend this list. I'm using a command called Mod
Example: Type in =Mod(100,13) to get 9
| n | 10^n mod 13 | | 1 | 10 | | 2 | 9 | | 3 | 12 | | 4 | 3 | | 5 | 4 | | 6 | 1 | | 7 | 10 | | 8 | 9 | | 9 | 12 | | 10 | 3 |
I'll leave the scratch work for the student to do.
The pattern is 10, 9, 12, 3, 4, 1, 10, 9...
Once reaching remainder 1, the pattern repeats over again.
This is simply because 1 times any number is that number.
There are 6 items in the set {10, 9, 12, 3, 4, 1}
So this means we'll divide 241 over 6 to look at the remainder (yes it seems a bit strange to change the modulus all of a sudden)
241/6 = 40 remainder 1
The remainder 1 means we'll look at the 1st slot of that 6 number repeating pattern. That 1st slot is 10.
Therefore we found another way to determine that
)
--------------------------------------------------------------------------------------------------------------------
A 3rd approach:
Let's look at terms of the form 10^(2^n) where n is a positive integer
Effectively we're repeatedly squaring powers of 10, since something like 10^4 is the squaring of 10^2; or 10^8 is the squaring of 10^4, etc
) mentioned in the previous section
^2 \equiv 3 (\text{mod } 13)) mentioned in the previous section
^2 \equiv \left(3\right)^2 \equiv 9 (\text{mod } 13))
^2 \equiv \left(9\right)^2 \equiv 81 \equiv 3 (\text{mod } 13)) because 81/13 = 6 remainder 3.
Keep this process going to generate this table
| n | 2^n | 10^(2^n) mod 13 | | 1 | 2 | 9 | | 2 | 4 | 3 | | 3 | 8 | 9 | | 4 | 16 | 3 | | 5 | 32 | 9 | | 6 | 64 | 3 | | 7 | 128 | 9 | | 8 |
256 | 3 |
We have a much nicer pattern going on here.
The remainder is either 9 or 3 depending if n is odd or even in that order.
Technically a table isn't needed, but it could be nice to have.
This is so we can break 241 into its binary components so to speak.
Refer to tutorials on how to convert from base 10 to base 2.
241 base 10 = 11110001 base 2
241 base 10 = 1*2^7 + 1*2^6 + 1*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 1*2^0
241 base 10 = 1*128 + 1*64 + 1*32 + 1*16 + 0*8 + 0*4 + 0*2 + 1*1
241 base 10 = 128 + 64 + 32 + 16 + 1
241 = 128 + 64 + 32 + 16 + 1
Then notice the following computation
)
)
) Use the table shown above. For example, 10^128 = 9 (mod 13)
*(9*3)*10 (\text{mod } 13))
*(27)*10 (\text{mod } 13))
*(1)*10 (\text{mod } 13)) because 27/13 = 2 remainder 1
--------------------------------------------------------------------------------------------------------------------
FLT is perhaps the best choice since it appears your professor has introduced it and is likely expecting you to use it; however, it's still good practice to be able to tackle problems in various ways.
For more practice, check out this similar question
https://www.algebra.com/algebra/homework/complex/Complex_Numbers.faq.question.1205936.html
Answer by Edwin McCravy(20056)  (Show Source):
You can put this solution on YOUR website!
I'll elaborate a little more on math_tutor2020's 2nd approach.
As he pointed out, even if you knew nothing about modular
arithmetic, and never heard of Fermat's little (or last)
theorem, you could do it with only long division, make an
indefinitely long string power of 10 like 1000000000000...
and start dividing
769230
13)1000000000000...
91
90
78
120
117
30
26
40
39
10
0
10
Now we see by the red remainders, that they are going to keep
going 10,9,12,3,4,1,... forever. That's a cycle of 6 remainders
since 101 had the reminder 10, we can find out by
division
48
6)241
24
1
This shows the remainders would go through the cycle of 6
48 times and since the remainder is 1, that means it had
started through the cycle the 49th time and was at the 1st
member of the cycle when it got to the 241st power of 10.
So the answer is the first member of the cycle, or 10.
No doubt Mr. Fermat started out this way and kept looking
for patterns, and even patterns of patterns, etc. and came
up with his little theorem.
Edwin
|
|
|
