Problem - Arithmetic: ''Solve 3^(64) mod 67 using Fermat's little theorem.''

[zhazzu]

The problem is:
''Solve 3^(64) mod 67 using Fermat's little theorem.''


Hi, My teacher explained it but just using letters. That's it, he explained it very abstract. Now, i would like to practice but i don't
know how to do it with numbers. And that's why i ask you. I have a list of 15 problems similiars to this one. I want to see one of them solved in order to be able to solve the others.

Another problem is the next one:
'' Find all the natural numbers which its last digit is 4, such that its double be congruent with 1 mod 3 and its triple congruent with 2 mod 7. And check the answer.''

 

[ksdhart]

Well, a good starting place is reviewing what, exactly, Fermat's Little Theorem says. Given two any integer a and any prime number p:

For any integer a, a^p - a is an integer multiple of p.
If a is not divisible by p, then a^{p - 1} - 1 is an integer multiple of p.

Or to write these statements with modular arithmetic symbols:

\(\displaystyle a^p\equiv a\,mod\,p\)

\(\displaystyle a^{p-1}\equiv 1\,mod\,p\) if a is not divisible by p

Based on this, let's tackle the first problem, ''Solve 3^(64) mod 67 using Fermat's little theorem.'' In both forms of the theorem above, you always work with mod p. That suggests that the value of p is 67, which is indeed a prime. And you're asked about the value of 3⁶⁴, which is not the same as 67. So, we'll use the second form of the theorem...

\(\displaystyle 3^{66}\equiv 1\,mod\,67\)

To express that in terms of 3⁶⁴, we can rewrite it as:

\(\displaystyle 3^2\cdot 3^{64}\equiv 1\,mod\,67\)

Can you continue from there? If you get stuck, that's okay. But when you reply back, please include all further workings, even if you know they're wrong.

----

As for the second problem, if we call the number n, we know these two things:

\(\displaystyle 2n\equiv 1\,mod\,3\)

\(\displaystyle 3n\equiv 2\,mod\,7\)

For this problem, I guess you could use Fermat's Little Theorem, but that's not the way I'd go about it. I'd make a table of values, with 5 columns. n, 2n, 3n, 2n mod 3, and 3n mod 7. Then fill in the appropriate values, and see if you can find a pattern.

 

[zhazzu]

arithmetic problem

Well, a good starting place is reviewing what, exactly, Fermat's Little Theorem says. Given two any integer a and any prime number p:



Or to write these statements with modular arithmetic symbols:

\(\displaystyle a^p\equiv a\,mod\,p\)

\(\displaystyle a^{p-1}\equiv 1\,mod\,p\) if a is not divisible by p

Based on this, let's tackle the first problem, ''Solve 3^(64) mod 67 using Fermat's little theorem.'' In both forms of the theorem above, you always work with mod p. That suggests that the value of p is 67, which is indeed a prime. And you're asked about the value of 3⁶⁴, which is not the same as 67. So, we'll use the second form of the theorem...

\(\displaystyle 3^{66}\equiv 1\,mod\,67\)

To express that in terms of 3⁶⁴, we can rewrite it as:

\(\displaystyle 3^2\cdot 3^{64}\equiv 1\,mod\,67\)

Can you continue from there? If you get stuck, that's okay. But when you reply back, please include all further workings, even if you know they're wrong.

----

As for the second problem, if we call the number n, we know these two things:

\(\displaystyle 2n\equiv 1\,mod\,3\)

\(\displaystyle 3n\equiv 2\,mod\,7\)

For this problem, I guess you could use Fermat's Little Theorem, but that's not the way I'd go about it. I'd make a table of values, with 5 columns. n, 2n, 3n, 2n mod 3, and 3n mod 7. Then fill in the appropriate values, and see if you can find a pattern.

1st problem: My teacher explained it but in a very abstract way (without examples, numbers...). I don't know how to do it. I've got a list of 15 problems about that and this is one of the problems. I would like to see this exercise solved in order to be able to do the other 14 problems of the list. I just ask the solution for the 1st problem.

2n problem: Thank you very much for the explanation. I'm going to try to solve it.

 

[zhazzu]

first problem

Well, a good starting place is reviewing what, exactly, Fermat's Little Theorem says. Given two any integer a and any prime number p:



Or to write these statements with modular arithmetic symbols:

\(\displaystyle a^p\equiv a\,mod\,p\)

\(\displaystyle a^{p-1}\equiv 1\,mod\,p\) if a is not divisible by p

Based on this, let's tackle the first problem, ''Solve 3^(64) mod 67 using Fermat's little theorem.'' In both forms of the theorem above, you always work with mod p. That suggests that the value of p is 67, which is indeed a prime. And you're asked about the value of 3⁶⁴, which is not the same as 67. So, we'll use the second form of the theorem...

\(\displaystyle 3^{66}\equiv 1\,mod\,67\)

To express that in terms of 3⁶⁴, we can rewrite it as:

\(\displaystyle 3^2\cdot 3^{64}\equiv 1\,mod\,67\)

Can you continue from there? If you get stuck, that's okay. But when you reply back, please include all further workings, even if you know they're wrong.

----

As for the second problem, if we call the number n, we know these two things:

\(\displaystyle 2n\equiv 1\,mod\,3\)

\(\displaystyle 3n\equiv 2\,mod\,7\)

For this problem, I guess you could use Fermat's Little Theorem, but that's not the way I'd go about it. I'd make a table of values, with 5 columns. n, 2n, 3n, 2n mod 3, and 3n mod 7. Then fill in the appropriate values, and see if you can find a pattern.

Is this right ??

By Fermat's Little Theorem, we know that 3^66 is congruent to 1 mod 67.

3^66 = (3^64)(3^2). Since 3^66 is 1 mod 67, 3^64 and 3^2 must be inverses of each
other mod 67. So to find the class of 3^64 mod 67, we need to find the class that's the
inverse of 3 mod 67 and square it.

To find the inverse of 3 mod 67, we'll need to solve the diophantine equation

3x + 67y = 1

Any x that solves this equation will be an inverse of 3 mod 67. I like to use Euclid's
algorithm for greatest common divisor to solve diophantine equations like this. That
involves repeated divisions with remainder, which for this equation goes this way:

67 = 3*22 + 1
3 = 1*3 + 0

We reached remainder 0 very quickly in this example. Since the last nonzero remainder
was 1, the greatest common divisor of 3 and 67 is 1 (which we already knew) and

3*(-22) + 67*1 = 1

Thus -22 is the inverse of 3 mod 67, and -22 is the same mod 67 as 45.

From our earlier work, we know that he square of 45 mod 67 will be congruent to 3^64
mod 67. So the last step is to square 45 and determine its class mod 67.

45^2 = 2025 and this is congruent to 15 mod 67.

So

2^64 = 15 mod 67

 

[ksdhart]

The only problem I see in your working is a minor typo at the very end. You say 2⁶⁴ = 15 mod 67. But shouldn't that be 3⁶⁴? That said, I got the same answer you did, so everything else seems fine to me. Good job.

 

[zhazzu]

mistake

ooh, it was just a mistake.
Thank you.