Mixing
(Modular Arithmetic) Congruences With Exponents
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I am trying to find the following:
The least positive integer $n$ for which
$3^n equiv 1$ (mod $7$)
And hence $3^100$ (mod $7$).
The least positive integer $n$ for which
$5^n equiv 1$ (mod $17$) or $5^n equiv -1$ (mod $17$)
And hence evaluate $5^243$ (mod $17$).
Evaluate $2^4$ (mod $18$) and hence evaluate $2^300$ (mod $18$).
I've learned how to use the Euclidean algorithm, but I have no idea how to compute congruence when they have exponents, as above. These seem very daunting to me. I would greatly appreciate it if people could please take the time to explain how this is done.
I will then post my work for each of these for, if possible, feedback on the solutions, since I do not have any solutions for these.
Thank you.
modular-arithmetic
asked Aug 25 at 10:09
The Pointer
2,7692832
add a comment |Â
up vote
2
down vote
favorite
I am trying to find the following:
The least positive integer $n$ for which
$3^n equiv 1$ (mod $7$)
And hence $3^100$ (mod $7$).
The least positive integer $n$ for which
$5^n equiv 1$ (mod $17$) or $5^n equiv -1$ (mod $17$)
And hence evaluate $5^243$ (mod $17$).
Evaluate $2^4$ (mod $18$) and hence evaluate $2^300$ (mod $18$).
I've learned how to use the Euclidean algorithm, but I have no idea how to compute congruence when they have exponents, as above. These seem very daunting to me. I would greatly appreciate it if people could please take the time to explain how this is done.
I will then post my work for each of these for, if possible, feedback on the solutions, since I do not have any solutions for these.
Thank you.
modular-arithmetic
asked Aug 25 at 10:09
The Pointer
2,7692832
Have you heard of Euler's totient function?
– Jazzachi
Aug 25 at 10:13
@Jazzachi No, and nor were we taught it. So I think my instructors want us to solve this through other means?
– The Pointer
Aug 25 at 10:14
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am trying to find the following:
The least positive integer $n$ for which
$3^n equiv 1$ (mod $7$)
And hence $3^100$ (mod $7$).
The least positive integer $n$ for which
$5^n equiv 1$ (mod $17$) or $5^n equiv -1$ (mod $17$)
And hence evaluate $5^243$ (mod $17$).
Evaluate $2^4$ (mod $18$) and hence evaluate $2^300$ (mod $18$).
I've learned how to use the Euclidean algorithm, but I have no idea how to compute congruence when they have exponents, as above. These seem very daunting to me. I would greatly appreciate it if people could please take the time to explain how this is done.
I will then post my work for each of these for, if possible, feedback on the solutions, since I do not have any solutions for these.
Thank you.
modular-arithmetic
asked Aug 25 at 10:09
The Pointer
2,7692832
I am trying to find the following:
The least positive integer $n$ for which
$3^n equiv 1$ (mod $7$)
And hence $3^100$ (mod $7$).
The least positive integer $n$ for which
$5^n equiv 1$ (mod $17$) or $5^n equiv -1$ (mod $17$)
And hence evaluate $5^243$ (mod $17$).
Evaluate $2^4$ (mod $18$) and hence evaluate $2^300$ (mod $18$).
I've learned how to use the Euclidean algorithm, but I have no idea how to compute congruence when they have exponents, as above. These seem very daunting to me. I would greatly appreciate it if people could please take the time to explain how this is done.
I will then post my work for each of these for, if possible, feedback on the solutions, since I do not have any solutions for these.
Thank you.
modular-arithmetic
asked Aug 25 at 10:09
The Pointer
2,7692832
edited Aug 25 at 10:29
asked Aug 25 at 10:09
The Pointer
2,7692832
asked Aug 25 at 10:09
The Pointer
2,7692832
asked Aug 25 at 10:09
The Pointer
2,7692832
2,7692832
Have you heard of Euler's totient function?
– Jazzachi
Aug 25 at 10:13
@Jazzachi No, and nor were we taught it. So I think my instructors want us to solve this through other means?
– The Pointer
Aug 25 at 10:14
add a comment |Â
Have you heard of Euler's totient function?
– Jazzachi
Aug 25 at 10:13
@Jazzachi No, and nor were we taught it. So I think my instructors want us to solve this through other means?
– The Pointer
Aug 25 at 10:14
Have you heard of Euler's totient function?
– Jazzachi
Aug 25 at 10:13
Have you heard of Euler's totient function?
– Jazzachi
Aug 25 at 10:13
@Jazzachi No, and nor were we taught it. So I think my instructors want us to solve this through other means?
– The Pointer
Aug 25 at 10:14
@Jazzachi No, and nor were we taught it. So I think my instructors want us to solve this through other means?
– The Pointer
Aug 25 at 10:14
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
Regarding congruences with exponents - the cool thing about them is you can raise 'each side' to some power, or multiply them by a common factor and it remains true. It's often useful to show that $x^nequiv pm 1 pmod k $. Regarding your first question, we know $3equiv 3pmod 7 $ so $3^2equiv 2pmod 7$ since $9pmod 7=2$. So $3^3=3^2times 3equiv 2times 3=6equiv -1 pmod 7$. So $3^3equiv -1 pmod 7$. Hence $(3^3)^2=3^6equiv (-1)^2=1pmod 7$. We know $3^100=3^6cdot 16+4=3^96cdot 3^3cdot 3$, and since we know the value of all these modulo $7$, $3^100$ is congruent mod $7$ to the product of them.
For your 2nd question, we can apply these same principles - it just takes a bit longer $$beginalign*5&equiv 5pmod 17 \ implies 5^2&equiv 8 pmod 17 \ implies 5^3&equiv 6pmod 17 qquad textsince $40pmod 17=6$ \ implies 5^4&equiv 13pmod 17qquad textsince $30pmod17=13$ \ &vdots \ implies 5^8&equiv -1pmod17endalign*$$Note that we could have directly obtained the final result by squaring both sides of the fourth line. So now $5^243=(5^8)^30cdot 5^3=dots$
However, using Euler's theorem is usually faster - there's examples of solutions to similar problems within that link.
edited Aug 25 at 11:30
The Pointer
2,7692832
answered Aug 25 at 10:39
Jazzachi
9011517
I just edited the missing $-1$ in for you.
– The Pointer
Aug 25 at 11:08
1
@ThePointer We know $3^3equiv -1 pmod 7$ so $3^6equiv 1pmod 7$. So $3^96equiv 1pmod 7$. We also know $3equiv 3pmod 7$. So $3^100=3^96times 3^3times 3equiv (1)(-1)(3)$, hence $3^100equiv 4pmod 7$.
– Jazzachi
Aug 25 at 11:12
So for the second one, we have $5^243=(5^8)^30cdot 5^4= 5^4 equiv 13$ (mod $17$)?
– The Pointer
Aug 25 at 11:27
1
@ThePointer Minor typo, should be $5^3$ not $5^4$. But your approach is correct, and since $5^3equiv 6 pmod 17$, $5^243equiv 6pmod 17$.
– Jazzachi
Aug 25 at 11:29
Ok, great, I think I understand it now! Thank you very much for taking the time to explain this to me. I found this very enlightening!
– The Pointer
Aug 25 at 11:31
add a comment |Â
up vote
2
down vote
Hint:
For the first two questions, Fermat's little theorem works because $7$ and $17$ are both prime. Now you can use the second form: $a^p-1 equiv 1 pmod p$ (if $a nmid p$ ).
For the last question, $2^4 pmod 18 equiv -2$. Then $(2^4)^4 = 2^16 equiv -2$, and $2^256 equiv -2$, so you can break up $300$ into powers of $4$.
answered Aug 25 at 10:15
Toby Mak
2,8221925
But this isn't a general way to solve these problems?
– The Pointer
Aug 25 at 10:19
@ThePointer It depends on the question. Luckily, this is an exercise, so they might want you to notice that $7$ and $17$ are both prime. If you have to use Euler's totient function, you might use the identity for $phi(mn)$ and carry on from there.
– Toby Mak
Aug 25 at 10:22
I don't understand why we use the second form? We don't even know what $p$ is, so how do we know whether to use the first or second form?
– The Pointer
Aug 25 at 10:31
@ThePointer We can use the second form because $a$ does not divide $p$ in your questions (if $p = 7$, $a$ is not $14, 21, 28$ etc.). $p$ is prime.
– Toby Mak
Aug 25 at 10:34
Hmm, I see. But the Wikipedia article also assumes that $n = p$? That doesn't necessarily have to be true for this problem, right? So is it valid for us to use this method?
– The Pointer
Aug 25 at 10:36
 |Â
show 2 more comments
up vote
0
down vote
Usually the standard routine is to use Euler's theorem which states that:
Let $ainBbb Z_n$, if $gcd(a,n)=1$ then $$a^phi(n)equiv_n 1$$
$phi(n)$ is called the Euler totient function, and it is the number of integers $k$ such that $1leq k<n$ and $gcd(k,n)=1$.
For instance $phi(10)=4$ because there are only four integers less than $10$, that are relatively prime (no common factor) to $10$. $$colorgreen1,2,colorgreen3,4,5,6,colorgreen7,8,colorgreen9$$ This means that $$a^4equiv_101$$ if $gcd(a,10)=1$. So $$1^4equiv_101\3^4equiv_101\7^4equiv_101\9^4equiv_101$$
When $n=p$ is prime $phi(p)=p-1$. With $p=5$ we have $$1^4equiv_51\2^4equiv_51\3^4equiv_51\4^4equiv_51$$ This special case, with $p$ prime, is known as Fermat's little theorem.
answered Aug 25 at 11:33
cansomeonehelpmeout
5,2883830
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Regarding congruences with exponents - the cool thing about them is you can raise 'each side' to some power, or multiply them by a common factor and it remains true. It's often useful to show that $x^nequiv pm 1 pmod k $. Regarding your first question, we know $3equiv 3pmod 7 $ so $3^2equiv 2pmod 7$ since $9pmod 7=2$. So $3^3=3^2times 3equiv 2times 3=6equiv -1 pmod 7$. So $3^3equiv -1 pmod 7$. Hence $(3^3)^2=3^6equiv (-1)^2=1pmod 7$. We know $3^100=3^6cdot 16+4=3^96cdot 3^3cdot 3$, and since we know the value of all these modulo $7$, $3^100$ is congruent mod $7$ to the product of them.
For your 2nd question, we can apply these same principles - it just takes a bit longer $$beginalign*5&equiv 5pmod 17 \ implies 5^2&equiv 8 pmod 17 \ implies 5^3&equiv 6pmod 17 qquad textsince $40pmod 17=6$ \ implies 5^4&equiv 13pmod 17qquad textsince $30pmod17=13$ \ &vdots \ implies 5^8&equiv -1pmod17endalign*$$Note that we could have directly obtained the final result by squaring both sides of the fourth line. So now $5^243=(5^8)^30cdot 5^3=dots$
However, using Euler's theorem is usually faster - there's examples of solutions to similar problems within that link.
edited Aug 25 at 11:30
The Pointer
2,7692832
answered Aug 25 at 10:39
Jazzachi
9011517
I just edited the missing $-1$ in for you.
– The Pointer
Aug 25 at 11:08
1
@ThePointer We know $3^3equiv -1 pmod 7$ so $3^6equiv 1pmod 7$. So $3^96equiv 1pmod 7$. We also know $3equiv 3pmod 7$. So $3^100=3^96times 3^3times 3equiv (1)(-1)(3)$, hence $3^100equiv 4pmod 7$.
– Jazzachi
Aug 25 at 11:12
So for the second one, we have $5^243=(5^8)^30cdot 5^4= 5^4 equiv 13$ (mod $17$)?
– The Pointer
Aug 25 at 11:27
1
@ThePointer Minor typo, should be $5^3$ not $5^4$. But your approach is correct, and since $5^3equiv 6 pmod 17$, $5^243equiv 6pmod 17$.
– Jazzachi
Aug 25 at 11:29
Ok, great, I think I understand it now! Thank you very much for taking the time to explain this to me. I found this very enlightening!
– The Pointer
Aug 25 at 11:31
add a comment |Â
up vote
3
down vote
accepted
Regarding congruences with exponents - the cool thing about them is you can raise 'each side' to some power, or multiply them by a common factor and it remains true. It's often useful to show that $x^nequiv pm 1 pmod k $. Regarding your first question, we know $3equiv 3pmod 7 $ so $3^2equiv 2pmod 7$ since $9pmod 7=2$. So $3^3=3^2times 3equiv 2times 3=6equiv -1 pmod 7$. So $3^3equiv -1 pmod 7$. Hence $(3^3)^2=3^6equiv (-1)^2=1pmod 7$. We know $3^100=3^6cdot 16+4=3^96cdot 3^3cdot 3$, and since we know the value of all these modulo $7$, $3^100$ is congruent mod $7$ to the product of them.
For your 2nd question, we can apply these same principles - it just takes a bit longer $$beginalign*5&equiv 5pmod 17 \ implies 5^2&equiv 8 pmod 17 \ implies 5^3&equiv 6pmod 17 qquad textsince $40pmod 17=6$ \ implies 5^4&equiv 13pmod 17qquad textsince $30pmod17=13$ \ &vdots \ implies 5^8&equiv -1pmod17endalign*$$Note that we could have directly obtained the final result by squaring both sides of the fourth line. So now $5^243=(5^8)^30cdot 5^3=dots$
However, using Euler's theorem is usually faster - there's examples of solutions to similar problems within that link.
edited Aug 25 at 11:30
The Pointer
2,7692832
answered Aug 25 at 10:39
Jazzachi
9011517
I just edited the missing $-1$ in for you.
– The Pointer
Aug 25 at 11:08
1
@ThePointer We know $3^3equiv -1 pmod 7$ so $3^6equiv 1pmod 7$. So $3^96equiv 1pmod 7$. We also know $3equiv 3pmod 7$. So $3^100=3^96times 3^3times 3equiv (1)(-1)(3)$, hence $3^100equiv 4pmod 7$.
– Jazzachi
Aug 25 at 11:12
So for the second one, we have $5^243=(5^8)^30cdot 5^4= 5^4 equiv 13$ (mod $17$)?
– The Pointer
Aug 25 at 11:27
1
@ThePointer Minor typo, should be $5^3$ not $5^4$. But your approach is correct, and since $5^3equiv 6 pmod 17$, $5^243equiv 6pmod 17$.
– Jazzachi
Aug 25 at 11:29
Ok, great, I think I understand it now! Thank you very much for taking the time to explain this to me. I found this very enlightening!
– The Pointer
Aug 25 at 11:31
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Regarding congruences with exponents - the cool thing about them is you can raise 'each side' to some power, or multiply them by a common factor and it remains true. It's often useful to show that $x^nequiv pm 1 pmod k $. Regarding your first question, we know $3equiv 3pmod 7 $ so $3^2equiv 2pmod 7$ since $9pmod 7=2$. So $3^3=3^2times 3equiv 2times 3=6equiv -1 pmod 7$. So $3^3equiv -1 pmod 7$. Hence $(3^3)^2=3^6equiv (-1)^2=1pmod 7$. We know $3^100=3^6cdot 16+4=3^96cdot 3^3cdot 3$, and since we know the value of all these modulo $7$, $3^100$ is congruent mod $7$ to the product of them.
For your 2nd question, we can apply these same principles - it just takes a bit longer $$beginalign*5&equiv 5pmod 17 \ implies 5^2&equiv 8 pmod 17 \ implies 5^3&equiv 6pmod 17 qquad textsince $40pmod 17=6$ \ implies 5^4&equiv 13pmod 17qquad textsince $30pmod17=13$ \ &vdots \ implies 5^8&equiv -1pmod17endalign*$$Note that we could have directly obtained the final result by squaring both sides of the fourth line. So now $5^243=(5^8)^30cdot 5^3=dots$
However, using Euler's theorem is usually faster - there's examples of solutions to similar problems within that link.
edited Aug 25 at 11:30
The Pointer
2,7692832
answered Aug 25 at 10:39
Jazzachi
9011517
Regarding congruences with exponents - the cool thing about them is you can raise 'each side' to some power, or multiply them by a common factor and it remains true. It's often useful to show that $x^nequiv pm 1 pmod k $. Regarding your first question, we know $3equiv 3pmod 7 $ so $3^2equiv 2pmod 7$ since $9pmod 7=2$. So $3^3=3^2times 3equiv 2times 3=6equiv -1 pmod 7$. So $3^3equiv -1 pmod 7$. Hence $(3^3)^2=3^6equiv (-1)^2=1pmod 7$. We know $3^100=3^6cdot 16+4=3^96cdot 3^3cdot 3$, and since we know the value of all these modulo $7$, $3^100$ is congruent mod $7$ to the product of them.
For your 2nd question, we can apply these same principles - it just takes a bit longer $$beginalign*5&equiv 5pmod 17 \ implies 5^2&equiv 8 pmod 17 \ implies 5^3&equiv 6pmod 17 qquad textsince $40pmod 17=6$ \ implies 5^4&equiv 13pmod 17qquad textsince $30pmod17=13$ \ &vdots \ implies 5^8&equiv -1pmod17endalign*$$Note that we could have directly obtained the final result by squaring both sides of the fourth line. So now $5^243=(5^8)^30cdot 5^3=dots$
However, using Euler's theorem is usually faster - there's examples of solutions to similar problems within that link.
edited Aug 25 at 11:30
The Pointer
2,7692832
answered Aug 25 at 10:39
Jazzachi
9011517
edited Aug 25 at 11:30
The Pointer
2,7692832
edited Aug 25 at 11:30
The Pointer
2,7692832
edited Aug 25 at 11:30
The Pointer
2,7692832
2,7692832
answered Aug 25 at 10:39
Jazzachi
9011517
answered Aug 25 at 10:39
Jazzachi
9011517
answered Aug 25 at 10:39
Jazzachi
9011517
9011517
I just edited the missing $-1$ in for you.
– The Pointer
Aug 25 at 11:08
1
@ThePointer We know $3^3equiv -1 pmod 7$ so $3^6equiv 1pmod 7$. So $3^96equiv 1pmod 7$. We also know $3equiv 3pmod 7$. So $3^100=3^96times 3^3times 3equiv (1)(-1)(3)$, hence $3^100equiv 4pmod 7$.
– Jazzachi
Aug 25 at 11:12
So for the second one, we have $5^243=(5^8)^30cdot 5^4= 5^4 equiv 13$ (mod $17$)?
– The Pointer
Aug 25 at 11:27
1
@ThePointer Minor typo, should be $5^3$ not $5^4$. But your approach is correct, and since $5^3equiv 6 pmod 17$, $5^243equiv 6pmod 17$.
– Jazzachi
Aug 25 at 11:29
Ok, great, I think I understand it now! Thank you very much for taking the time to explain this to me. I found this very enlightening!
– The Pointer
Aug 25 at 11:31
add a comment |Â
I just edited the missing $-1$ in for you.
– The Pointer
Aug 25 at 11:08
1
@ThePointer We know $3^3equiv -1 pmod 7$ so $3^6equiv 1pmod 7$. So $3^96equiv 1pmod 7$. We also know $3equiv 3pmod 7$. So $3^100=3^96times 3^3times 3equiv (1)(-1)(3)$, hence $3^100equiv 4pmod 7$.
– Jazzachi
Aug 25 at 11:12
So for the second one, we have $5^243=(5^8)^30cdot 5^4= 5^4 equiv 13$ (mod $17$)?
– The Pointer
Aug 25 at 11:27
1
@ThePointer Minor typo, should be $5^3$ not $5^4$. But your approach is correct, and since $5^3equiv 6 pmod 17$, $5^243equiv 6pmod 17$.
– Jazzachi
Aug 25 at 11:29
Ok, great, I think I understand it now! Thank you very much for taking the time to explain this to me. I found this very enlightening!
– The Pointer
Aug 25 at 11:31
I just edited the missing $-1$ in for you.
– The Pointer
Aug 25 at 11:08
I just edited the missing $-1$ in for you.
– The Pointer
Aug 25 at 11:08
1
1
@ThePointer We know $3^3equiv -1 pmod 7$ so $3^6equiv 1pmod 7$. So $3^96equiv 1pmod 7$. We also know $3equiv 3pmod 7$. So $3^100=3^96times 3^3times 3equiv (1)(-1)(3)$, hence $3^100equiv 4pmod 7$.
– Jazzachi
Aug 25 at 11:12
@ThePointer We know $3^3equiv -1 pmod 7$ so $3^6equiv 1pmod 7$. So $3^96equiv 1pmod 7$. We also know $3equiv 3pmod 7$. So $3^100=3^96times 3^3times 3equiv (1)(-1)(3)$, hence $3^100equiv 4pmod 7$.
– Jazzachi
Aug 25 at 11:12
So for the second one, we have $5^243=(5^8)^30cdot 5^4= 5^4 equiv 13$ (mod $17$)?
– The Pointer
Aug 25 at 11:27
So for the second one, we have $5^243=(5^8)^30cdot 5^4= 5^4 equiv 13$ (mod $17$)?
– The Pointer
Aug 25 at 11:27
1
1
@ThePointer Minor typo, should be $5^3$ not $5^4$. But your approach is correct, and since $5^3equiv 6 pmod 17$, $5^243equiv 6pmod 17$.
– Jazzachi
Aug 25 at 11:29
@ThePointer Minor typo, should be $5^3$ not $5^4$. But your approach is correct, and since $5^3equiv 6 pmod 17$, $5^243equiv 6pmod 17$.
– Jazzachi
Aug 25 at 11:29
Ok, great, I think I understand it now! Thank you very much for taking the time to explain this to me. I found this very enlightening!
– The Pointer
Aug 25 at 11:31
Ok, great, I think I understand it now! Thank you very much for taking the time to explain this to me. I found this very enlightening!
– The Pointer
Aug 25 at 11:31
add a comment |Â
up vote
2
down vote
Hint:
For the first two questions, Fermat's little theorem works because $7$ and $17$ are both prime. Now you can use the second form: $a^p-1 equiv 1 pmod p$ (if $a nmid p$ ).
For the last question, $2^4 pmod 18 equiv -2$. Then $(2^4)^4 = 2^16 equiv -2$, and $2^256 equiv -2$, so you can break up $300$ into powers of $4$.
answered Aug 25 at 10:15
Toby Mak
2,8221925
But this isn't a general way to solve these problems?
– The Pointer
Aug 25 at 10:19
@ThePointer It depends on the question. Luckily, this is an exercise, so they might want you to notice that $7$ and $17$ are both prime. If you have to use Euler's totient function, you might use the identity for $phi(mn)$ and carry on from there.
– Toby Mak
Aug 25 at 10:22
I don't understand why we use the second form? We don't even know what $p$ is, so how do we know whether to use the first or second form?
– The Pointer
Aug 25 at 10:31
@ThePointer We can use the second form because $a$ does not divide $p$ in your questions (if $p = 7$, $a$ is not $14, 21, 28$ etc.). $p$ is prime.
– Toby Mak
Aug 25 at 10:34
Hmm, I see. But the Wikipedia article also assumes that $n = p$? That doesn't necessarily have to be true for this problem, right? So is it valid for us to use this method?
– The Pointer
Aug 25 at 10:36
 |Â
show 2 more comments
up vote
2
down vote
Hint:
For the first two questions, Fermat's little theorem works because $7$ and $17$ are both prime. Now you can use the second form: $a^p-1 equiv 1 pmod p$ (if $a nmid p$ ).
For the last question, $2^4 pmod 18 equiv -2$. Then $(2^4)^4 = 2^16 equiv -2$, and $2^256 equiv -2$, so you can break up $300$ into powers of $4$.
answered Aug 25 at 10:15
Toby Mak
2,8221925
But this isn't a general way to solve these problems?
– The Pointer
Aug 25 at 10:19
@ThePointer It depends on the question. Luckily, this is an exercise, so they might want you to notice that $7$ and $17$ are both prime. If you have to use Euler's totient function, you might use the identity for $phi(mn)$ and carry on from there.
– Toby Mak
Aug 25 at 10:22
I don't understand why we use the second form? We don't even know what $p$ is, so how do we know whether to use the first or second form?
– The Pointer
Aug 25 at 10:31
@ThePointer We can use the second form because $a$ does not divide $p$ in your questions (if $p = 7$, $a$ is not $14, 21, 28$ etc.). $p$ is prime.
– Toby Mak
Aug 25 at 10:34
Hmm, I see. But the Wikipedia article also assumes that $n = p$? That doesn't necessarily have to be true for this problem, right? So is it valid for us to use this method?
– The Pointer
Aug 25 at 10:36
 |Â
show 2 more comments
up vote
2
down vote
up vote
2
down vote
Hint:
For the first two questions, Fermat's little theorem works because $7$ and $17$ are both prime. Now you can use the second form: $a^p-1 equiv 1 pmod p$ (if $a nmid p$ ).
For the last question, $2^4 pmod 18 equiv -2$. Then $(2^4)^4 = 2^16 equiv -2$, and $2^256 equiv -2$, so you can break up $300$ into powers of $4$.
answered Aug 25 at 10:15
Toby Mak
2,8221925
Hint:
For the first two questions, Fermat's little theorem works because $7$ and $17$ are both prime. Now you can use the second form: $a^p-1 equiv 1 pmod p$ (if $a nmid p$ ).
For the last question, $2^4 pmod 18 equiv -2$. Then $(2^4)^4 = 2^16 equiv -2$, and $2^256 equiv -2$, so you can break up $300$ into powers of $4$.
answered Aug 25 at 10:15
Toby Mak
2,8221925
edited Aug 25 at 10:23
answered Aug 25 at 10:15
Toby Mak
2,8221925
answered Aug 25 at 10:15
Toby Mak
2,8221925
answered Aug 25 at 10:15
Toby Mak
2,8221925
2,8221925
But this isn't a general way to solve these problems?
– The Pointer
Aug 25 at 10:19
@ThePointer It depends on the question. Luckily, this is an exercise, so they might want you to notice that $7$ and $17$ are both prime. If you have to use Euler's totient function, you might use the identity for $phi(mn)$ and carry on from there.
– Toby Mak
Aug 25 at 10:22
I don't understand why we use the second form? We don't even know what $p$ is, so how do we know whether to use the first or second form?
– The Pointer
Aug 25 at 10:31
@ThePointer We can use the second form because $a$ does not divide $p$ in your questions (if $p = 7$, $a$ is not $14, 21, 28$ etc.). $p$ is prime.
– Toby Mak
Aug 25 at 10:34
Hmm, I see. But the Wikipedia article also assumes that $n = p$? That doesn't necessarily have to be true for this problem, right? So is it valid for us to use this method?
– The Pointer
Aug 25 at 10:36
 |Â
show 2 more comments
But this isn't a general way to solve these problems?
– The Pointer
Aug 25 at 10:19
@ThePointer It depends on the question. Luckily, this is an exercise, so they might want you to notice that $7$ and $17$ are both prime. If you have to use Euler's totient function, you might use the identity for $phi(mn)$ and carry on from there.
– Toby Mak
Aug 25 at 10:22
I don't understand why we use the second form? We don't even know what $p$ is, so how do we know whether to use the first or second form?
– The Pointer
Aug 25 at 10:31
@ThePointer We can use the second form because $a$ does not divide $p$ in your questions (if $p = 7$, $a$ is not $14, 21, 28$ etc.). $p$ is prime.
– Toby Mak
Aug 25 at 10:34
Hmm, I see. But the Wikipedia article also assumes that $n = p$? That doesn't necessarily have to be true for this problem, right? So is it valid for us to use this method?
– The Pointer
Aug 25 at 10:36
But this isn't a general way to solve these problems?
– The Pointer
Aug 25 at 10:19
But this isn't a general way to solve these problems?
– The Pointer
Aug 25 at 10:19
@ThePointer It depends on the question. Luckily, this is an exercise, so they might want you to notice that $7$ and $17$ are both prime. If you have to use Euler's totient function, you might use the identity for $phi(mn)$ and carry on from there.
– Toby Mak
Aug 25 at 10:22
@ThePointer It depends on the question. Luckily, this is an exercise, so they might want you to notice that $7$ and $17$ are both prime. If you have to use Euler's totient function, you might use the identity for $phi(mn)$ and carry on from there.
– Toby Mak
Aug 25 at 10:22
I don't understand why we use the second form? We don't even know what $p$ is, so how do we know whether to use the first or second form?
– The Pointer
Aug 25 at 10:31
I don't understand why we use the second form? We don't even know what $p$ is, so how do we know whether to use the first or second form?
– The Pointer
Aug 25 at 10:31
@ThePointer We can use the second form because $a$ does not divide $p$ in your questions (if $p = 7$, $a$ is not $14, 21, 28$ etc.). $p$ is prime.
– Toby Mak
Aug 25 at 10:34
@ThePointer We can use the second form because $a$ does not divide $p$ in your questions (if $p = 7$, $a$ is not $14, 21, 28$ etc.). $p$ is prime.
– Toby Mak
Aug 25 at 10:34
Hmm, I see. But the Wikipedia article also assumes that $n = p$? That doesn't necessarily have to be true for this problem, right? So is it valid for us to use this method?
– The Pointer
Aug 25 at 10:36
Hmm, I see. But the Wikipedia article also assumes that $n = p$? That doesn't necessarily have to be true for this problem, right? So is it valid for us to use this method?
– The Pointer
Aug 25 at 10:36
 |Â
show 2 more comments
up vote
0
down vote
Usually the standard routine is to use Euler's theorem which states that:
Let $ainBbb Z_n$, if $gcd(a,n)=1$ then $$a^phi(n)equiv_n 1$$
$phi(n)$ is called the Euler totient function, and it is the number of integers $k$ such that $1leq k<n$ and $gcd(k,n)=1$.
For instance $phi(10)=4$ because there are only four integers less than $10$, that are relatively prime (no common factor) to $10$. $$colorgreen1,2,colorgreen3,4,5,6,colorgreen7,8,colorgreen9$$ This means that $$a^4equiv_101$$ if $gcd(a,10)=1$. So $$1^4equiv_101\3^4equiv_101\7^4equiv_101\9^4equiv_101$$
When $n=p$ is prime $phi(p)=p-1$. With $p=5$ we have $$1^4equiv_51\2^4equiv_51\3^4equiv_51\4^4equiv_51$$ This special case, with $p$ prime, is known as Fermat's little theorem.
answered Aug 25 at 11:33
cansomeonehelpmeout
5,2883830
add a comment |Â
up vote
0
down vote
Usually the standard routine is to use Euler's theorem which states that:
Let $ainBbb Z_n$, if $gcd(a,n)=1$ then $$a^phi(n)equiv_n 1$$
$phi(n)$ is called the Euler totient function, and it is the number of integers $k$ such that $1leq k<n$ and $gcd(k,n)=1$.
For instance $phi(10)=4$ because there are only four integers less than $10$, that are relatively prime (no common factor) to $10$. $$colorgreen1,2,colorgreen3,4,5,6,colorgreen7,8,colorgreen9$$ This means that $$a^4equiv_101$$ if $gcd(a,10)=1$. So $$1^4equiv_101\3^4equiv_101\7^4equiv_101\9^4equiv_101$$
When $n=p$ is prime $phi(p)=p-1$. With $p=5$ we have $$1^4equiv_51\2^4equiv_51\3^4equiv_51\4^4equiv_51$$ This special case, with $p$ prime, is known as Fermat's little theorem.
answered Aug 25 at 11:33
cansomeonehelpmeout
5,2883830
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Usually the standard routine is to use Euler's theorem which states that:
Let $ainBbb Z_n$, if $gcd(a,n)=1$ then $$a^phi(n)equiv_n 1$$
$phi(n)$ is called the Euler totient function, and it is the number of integers $k$ such that $1leq k<n$ and $gcd(k,n)=1$.
For instance $phi(10)=4$ because there are only four integers less than $10$, that are relatively prime (no common factor) to $10$. $$colorgreen1,2,colorgreen3,4,5,6,colorgreen7,8,colorgreen9$$ This means that $$a^4equiv_101$$ if $gcd(a,10)=1$. So $$1^4equiv_101\3^4equiv_101\7^4equiv_101\9^4equiv_101$$
When $n=p$ is prime $phi(p)=p-1$. With $p=5$ we have $$1^4equiv_51\2^4equiv_51\3^4equiv_51\4^4equiv_51$$ This special case, with $p$ prime, is known as Fermat's little theorem.
answered Aug 25 at 11:33
cansomeonehelpmeout
5,2883830
Usually the standard routine is to use Euler's theorem which states that:
Let $ainBbb Z_n$, if $gcd(a,n)=1$ then $$a^phi(n)equiv_n 1$$
$phi(n)$ is called the Euler totient function, and it is the number of integers $k$ such that $1leq k<n$ and $gcd(k,n)=1$.
For instance $phi(10)=4$ because there are only four integers less than $10$, that are relatively prime (no common factor) to $10$. $$colorgreen1,2,colorgreen3,4,5,6,colorgreen7,8,colorgreen9$$ This means that $$a^4equiv_101$$ if $gcd(a,10)=1$. So $$1^4equiv_101\3^4equiv_101\7^4equiv_101\9^4equiv_101$$
When $n=p$ is prime $phi(p)=p-1$. With $p=5$ we have $$1^4equiv_51\2^4equiv_51\3^4equiv_51\4^4equiv_51$$ This special case, with $p$ prime, is known as Fermat's little theorem.
answered Aug 25 at 11:33
cansomeonehelpmeout
5,2883830
edited Aug 25 at 11:40
answered Aug 25 at 11:33
cansomeonehelpmeout
5,2883830
answered Aug 25 at 11:33
cansomeonehelpmeout
5,2883830
answered Aug 25 at 11:33
cansomeonehelpmeout
5,2883830
5,2883830
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2893975%2fmodular-arithmetic-congruences-with-exponents%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Have you heard of Euler's totient function?
– Jazzachi
Aug 25 at 10:13
@Jazzachi No, and nor were we taught it. So I think my instructors want us to solve this through other means?
– The Pointer
Aug 25 at 10:14