Mixing
Why does the Euler's totient function $phi(n)$ give the minimum of exponent s.t. $a^{phi(n)}equiv 1pmod n$,...
$begingroup$
I want to know whether it's possible that there would exist $1lt kltphi(n)$ s.t. $a^{phi(n)}equiv 1pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)
OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^kequiv 1pmod n,$ given $(a,n)=1$.
number-theory
edited Jan 8 at 2:54
kale
33
asked Jan 7 at 18:45
user7813604user7813604
15912
$endgroup$
add a comment |
$begingroup$
I want to know whether it's possible that there would exist $1lt kltphi(n)$ s.t. $a^{phi(n)}equiv 1pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)
OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^kequiv 1pmod n,$ given $(a,n)=1$.
number-theory
edited Jan 8 at 2:54
kale
33
asked Jan 7 at 18:45
user7813604user7813604
15912
$endgroup$
1
$begingroup$
See this answer for order algorithms.
$endgroup$
– Bill Dubuque
Jan 7 at 19:40
$begingroup$
Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
$endgroup$
– Erick Wong
Jan 7 at 20:14
$begingroup$
@ErickWong: for the given $a$, sorry for confusing.
$endgroup$
– user7813604
Jan 8 at 1:48
add a comment |
$begingroup$
I want to know whether it's possible that there would exist $1lt kltphi(n)$ s.t. $a^{phi(n)}equiv 1pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)
OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^kequiv 1pmod n,$ given $(a,n)=1$.
number-theory
edited Jan 8 at 2:54
kale
33
asked Jan 7 at 18:45
user7813604user7813604
15912
$endgroup$
I want to know whether it's possible that there would exist $1lt kltphi(n)$ s.t. $a^{phi(n)}equiv 1pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)
OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^kequiv 1pmod n,$ given $(a,n)=1$.
number-theory
number-theory
edited Jan 8 at 2:54
kale
33
asked Jan 7 at 18:45
user7813604user7813604
15912
edited Jan 8 at 2:54
kale
33
asked Jan 7 at 18:45
user7813604user7813604
15912
edited Jan 8 at 2:54
kale
33
edited Jan 8 at 2:54
kale
33
edited Jan 8 at 2:54
kale
33
33
asked Jan 7 at 18:45
user7813604user7813604
15912
asked Jan 7 at 18:45
user7813604user7813604
15912
asked Jan 7 at 18:45
user7813604user7813604
15912
15912
1
$begingroup$
See this answer for order algorithms.
$endgroup$
– Bill Dubuque
Jan 7 at 19:40
$begingroup$
Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
$endgroup$
– Erick Wong
Jan 7 at 20:14
$begingroup$
@ErickWong: for the given $a$, sorry for confusing.
$endgroup$
– user7813604
Jan 8 at 1:48
add a comment |
1
$begingroup$
See this answer for order algorithms.
$endgroup$
– Bill Dubuque
Jan 7 at 19:40
$begingroup$
Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
$endgroup$
– Erick Wong
Jan 7 at 20:14
$begingroup$
@ErickWong: for the given $a$, sorry for confusing.
$endgroup$
– user7813604
Jan 8 at 1:48
1
1
$begingroup$
See this answer for order algorithms.
$endgroup$
– Bill Dubuque
Jan 7 at 19:40
$begingroup$
See this answer for order algorithms.
$endgroup$
– Bill Dubuque
Jan 7 at 19:40
$begingroup$
Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
$endgroup$
– Erick Wong
Jan 7 at 20:14
$begingroup$
Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
$endgroup$
– Erick Wong
Jan 7 at 20:14
$begingroup$
@ErickWong: for the given $a$, sorry for confusing.
$endgroup$
– user7813604
Jan 8 at 1:48
$begingroup$
@ErickWong: for the given $a$, sorry for confusing.
$endgroup$
– user7813604
Jan 8 at 1:48
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
$phi(7)=6$ but $2^3equiv 1$(mod$7$).
Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.
answered Jan 7 at 18:46
MarkMark
6,738416
$endgroup$
1
$begingroup$
Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
$endgroup$
– Mark
Jan 7 at 19:06
$begingroup$
that RSA is secure because $phi(n)$ is hard to find right? I just haven't connected these ideas...
$endgroup$
– user7813604
Jan 7 at 19:07
1
$begingroup$
Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
$endgroup$
– Mark
Jan 7 at 19:12
$begingroup$
Very grateful for your kindness and detailed explanation.
$endgroup$
– user7813604
Jan 7 at 19:15
$begingroup$
You're welcome.
$endgroup$
– Mark
Jan 7 at 19:17
|
show 3 more comments
$begingroup$
Hint 1:
If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.
Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.
Hint 2:
$(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....
Hint 3:
$a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?
=====
Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!
Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.
One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.
answered Jan 8 at 2:38
fleabloodfleablood
69.5k22685
$endgroup$
add a comment |
$begingroup$
Hint:
$$frac{10^3-1}{37}=27$$
answered Jan 7 at 18:48
ajotatxeajotatxe
53.8k23890
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065332%2fwhy-does-the-eulers-totient-function-phin-give-the-minimum-of-exponent-s-t%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$phi(7)=6$ but $2^3equiv 1$(mod$7$).
Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.
answered Jan 7 at 18:46
MarkMark
6,738416
$endgroup$
1
$begingroup$
Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
$endgroup$
– Mark
Jan 7 at 19:06
$begingroup$
that RSA is secure because $phi(n)$ is hard to find right? I just haven't connected these ideas...
$endgroup$
– user7813604
Jan 7 at 19:07
1
$begingroup$
Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
$endgroup$
– Mark
Jan 7 at 19:12
$begingroup$
Very grateful for your kindness and detailed explanation.
$endgroup$
– user7813604
Jan 7 at 19:15
$begingroup$
You're welcome.
$endgroup$
– Mark
Jan 7 at 19:17
|
show 3 more comments
$begingroup$
$phi(7)=6$ but $2^3equiv 1$(mod$7$).
Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.
answered Jan 7 at 18:46
MarkMark
6,738416
$endgroup$
1
$begingroup$
Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
$endgroup$
– Mark
Jan 7 at 19:06
$begingroup$
that RSA is secure because $phi(n)$ is hard to find right? I just haven't connected these ideas...
$endgroup$
– user7813604
Jan 7 at 19:07
1
$begingroup$
Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
$endgroup$
– Mark
Jan 7 at 19:12
$begingroup$
Very grateful for your kindness and detailed explanation.
$endgroup$
– user7813604
Jan 7 at 19:15
$begingroup$
You're welcome.
$endgroup$
– Mark
Jan 7 at 19:17
|
show 3 more comments
$begingroup$
$phi(7)=6$ but $2^3equiv 1$(mod$7$).
Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.
answered Jan 7 at 18:46
MarkMark
6,738416
$endgroup$
$phi(7)=6$ but $2^3equiv 1$(mod$7$).
Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.
answered Jan 7 at 18:46
MarkMark
6,738416
edited Jan 7 at 18:59
answered Jan 7 at 18:46
MarkMark
6,738416
answered Jan 7 at 18:46
MarkMark
6,738416
answered Jan 7 at 18:46
MarkMark
6,738416
6,738416
1
$begingroup$
Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
$endgroup$
– Mark
Jan 7 at 19:06
$begingroup$
that RSA is secure because $phi(n)$ is hard to find right? I just haven't connected these ideas...
$endgroup$
– user7813604
Jan 7 at 19:07
1
$begingroup$
Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
$endgroup$
– Mark
Jan 7 at 19:12
$begingroup$
Very grateful for your kindness and detailed explanation.
$endgroup$
– user7813604
Jan 7 at 19:15
$begingroup$
You're welcome.
$endgroup$
– Mark
Jan 7 at 19:17
|
show 3 more comments
1
$begingroup$
Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
$endgroup$
– Mark
Jan 7 at 19:06
$begingroup$
that RSA is secure because $phi(n)$ is hard to find right? I just haven't connected these ideas...
$endgroup$
– user7813604
Jan 7 at 19:07
1
$begingroup$
Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
$endgroup$
– Mark
Jan 7 at 19:12
$begingroup$
Very grateful for your kindness and detailed explanation.
$endgroup$
– user7813604
Jan 7 at 19:15
$begingroup$
You're welcome.
$endgroup$
– Mark
Jan 7 at 19:17
1
1
$begingroup$
Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
$endgroup$
– Mark
Jan 7 at 19:06
$begingroup$
Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
$endgroup$
– Mark
Jan 7 at 19:06
$begingroup$
that RSA is secure because $phi(n)$ is hard to find right? I just haven't connected these ideas...
$endgroup$
– user7813604
Jan 7 at 19:07
$begingroup$
that RSA is secure because $phi(n)$ is hard to find right? I just haven't connected these ideas...
$endgroup$
– user7813604
Jan 7 at 19:07
1
1
$begingroup$
Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
$endgroup$
– Mark
Jan 7 at 19:12
$begingroup$
Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
$endgroup$
– Mark
Jan 7 at 19:12
$begingroup$
Very grateful for your kindness and detailed explanation.
$endgroup$
– user7813604
Jan 7 at 19:15
$begingroup$
Very grateful for your kindness and detailed explanation.
$endgroup$
– user7813604
Jan 7 at 19:15
$begingroup$
You're welcome.
$endgroup$
– Mark
Jan 7 at 19:17
$begingroup$
You're welcome.
$endgroup$
– Mark
Jan 7 at 19:17
|
show 3 more comments
$begingroup$
Hint 1:
If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.
Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.
Hint 2:
$(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....
Hint 3:
$a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?
=====
Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!
Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.
One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.
answered Jan 8 at 2:38
fleabloodfleablood
69.5k22685
$endgroup$
add a comment |
$begingroup$
Hint 1:
If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.
Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.
Hint 2:
$(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....
Hint 3:
$a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?
=====
Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!
Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.
One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.
answered Jan 8 at 2:38
fleabloodfleablood
69.5k22685
$endgroup$
add a comment |
$begingroup$
Hint 1:
If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.
Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.
Hint 2:
$(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....
Hint 3:
$a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?
=====
Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!
Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.
One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.
answered Jan 8 at 2:38
fleabloodfleablood
69.5k22685
$endgroup$
Hint 1:
If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.
Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.
Hint 2:
$(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....
Hint 3:
$a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?
=====
Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!
Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.
One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.
answered Jan 8 at 2:38
fleabloodfleablood
69.5k22685
edited Jan 8 at 3:18
answered Jan 8 at 2:38
fleabloodfleablood
69.5k22685
answered Jan 8 at 2:38
fleabloodfleablood
69.5k22685
answered Jan 8 at 2:38
fleabloodfleablood
69.5k22685
69.5k22685
add a comment |
add a comment |
$begingroup$
Hint:
$$frac{10^3-1}{37}=27$$
answered Jan 7 at 18:48
ajotatxeajotatxe
53.8k23890
$endgroup$
add a comment |
$begingroup$
Hint:
$$frac{10^3-1}{37}=27$$
answered Jan 7 at 18:48
ajotatxeajotatxe
53.8k23890
$endgroup$
add a comment |
$begingroup$
Hint:
$$frac{10^3-1}{37}=27$$
answered Jan 7 at 18:48
ajotatxeajotatxe
53.8k23890
$endgroup$
Hint:
$$frac{10^3-1}{37}=27$$
answered Jan 7 at 18:48
ajotatxeajotatxe
53.8k23890
answered Jan 7 at 18:48
ajotatxeajotatxe
53.8k23890
answered Jan 7 at 18:48
ajotatxeajotatxe
53.8k23890
answered Jan 7 at 18:48
ajotatxeajotatxe
53.8k23890
53.8k23890
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065332%2fwhy-does-the-eulers-totient-function-phin-give-the-minimum-of-exponent-s-t%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
See this answer for order algorithms.
$endgroup$
– Bill Dubuque
Jan 7 at 19:40
$begingroup$
Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
$endgroup$
– Erick Wong
Jan 7 at 20:14
$begingroup$
@ErickWong: for the given $a$, sorry for confusing.
$endgroup$
– user7813604
Jan 8 at 1:48