Mixing
Modulo computing without Euler's theorem
1
$begingroup$
How would one compute the following congruence without applying Euler's theorem(since it is not possible anyway) and without using calculator?
$2^{1150} equiv x $ (mod $5^6$)
modular-arithmetic problem-solving
asked Jan 23 at 13:18
Michael MuntaMichael Munta
85111
$endgroup$
add a comment |
1
$begingroup$
How would one compute the following congruence without applying Euler's theorem(since it is not possible anyway) and without using calculator?
$2^{1150} equiv x $ (mod $5^6$)
modular-arithmetic problem-solving
asked Jan 23 at 13:18
Michael MuntaMichael Munta
85111
$endgroup$
1
$begingroup$
I wouldn't say Euler's theorem is impossible to use. But it doesn't help much, no.
$endgroup$
– Arthur
Jan 23 at 13:26
3
$begingroup$
Perhaps $$2^{1150}=(5-1)^{575}equiv-1+binom{575}{1}5-binom{575}{2}5^2+binom{575}{3}5^3pmod{5^6}$$ may be helpful...?
$endgroup$
– Sangchul Lee
Jan 23 at 13:31
$begingroup$
@SangchulLee What happened to $binom{575}45^4$ and $binom{575}55^5$?
$endgroup$
– Arthur
Jan 23 at 13:33
1
$begingroup$
@Arthur, I utilized $575=5^2times23$, which shows $5^2midbinom{575}{4}$ and $5midbinom{575}{5}$
$endgroup$
– Sangchul Lee
Jan 23 at 13:34
$begingroup$
Well, Euler's Th. can be of some use here as it does give us the relations: $x = 4 + 5i; ~ x = -1 + 25j; ~ x = -1+125k$, where $x = 2^{1150} mod 5^6$. All these relations can be easily generated without any need for a calculator (I did it within 2 minutes). You just need Euler's theorem, know basic properties of the totient function and possess elementary knowledge of group theory, especially group generators and the related tests.
$endgroup$
– Novice Geek
Jan 23 at 15:14
add a comment |
1
1
1
2
$begingroup$
How would one compute the following congruence without applying Euler's theorem(since it is not possible anyway) and without using calculator?
$2^{1150} equiv x $ (mod $5^6$)
modular-arithmetic problem-solving
asked Jan 23 at 13:18
Michael MuntaMichael Munta
85111
$endgroup$
How would one compute the following congruence without applying Euler's theorem(since it is not possible anyway) and without using calculator?
$2^{1150} equiv x $ (mod $5^6$)
modular-arithmetic problem-solving
modular-arithmetic problem-solving
asked Jan 23 at 13:18
Michael MuntaMichael Munta
85111
asked Jan 23 at 13:18
Michael MuntaMichael Munta
85111
asked Jan 23 at 13:18
Michael MuntaMichael Munta
85111
asked Jan 23 at 13:18
Michael MuntaMichael Munta
85111
asked Jan 23 at 13:18
Michael MuntaMichael Munta
85111
85111
1
$begingroup$
I wouldn't say Euler's theorem is impossible to use. But it doesn't help much, no.
$endgroup$
– Arthur
Jan 23 at 13:26
3
$begingroup$
Perhaps $$2^{1150}=(5-1)^{575}equiv-1+binom{575}{1}5-binom{575}{2}5^2+binom{575}{3}5^3pmod{5^6}$$ may be helpful...?
$endgroup$
– Sangchul Lee
Jan 23 at 13:31
$begingroup$
@SangchulLee What happened to $binom{575}45^4$ and $binom{575}55^5$?
$endgroup$
– Arthur
Jan 23 at 13:33
1
$begingroup$
@Arthur, I utilized $575=5^2times23$, which shows $5^2midbinom{575}{4}$ and $5midbinom{575}{5}$
$endgroup$
– Sangchul Lee
Jan 23 at 13:34
$begingroup$
Well, Euler's Th. can be of some use here as it does give us the relations: $x = 4 + 5i; ~ x = -1 + 25j; ~ x = -1+125k$, where $x = 2^{1150} mod 5^6$. All these relations can be easily generated without any need for a calculator (I did it within 2 minutes). You just need Euler's theorem, know basic properties of the totient function and possess elementary knowledge of group theory, especially group generators and the related tests.
$endgroup$
– Novice Geek
Jan 23 at 15:14
add a comment |
1
$begingroup$
I wouldn't say Euler's theorem is impossible to use. But it doesn't help much, no.
$endgroup$
– Arthur
Jan 23 at 13:26
3
$begingroup$
Perhaps $$2^{1150}=(5-1)^{575}equiv-1+binom{575}{1}5-binom{575}{2}5^2+binom{575}{3}5^3pmod{5^6}$$ may be helpful...?
$endgroup$
– Sangchul Lee
Jan 23 at 13:31
$begingroup$
@SangchulLee What happened to $binom{575}45^4$ and $binom{575}55^5$?
$endgroup$
– Arthur
Jan 23 at 13:33
1
$begingroup$
@Arthur, I utilized $575=5^2times23$, which shows $5^2midbinom{575}{4}$ and $5midbinom{575}{5}$
$endgroup$
– Sangchul Lee
Jan 23 at 13:34
$begingroup$
Well, Euler's Th. can be of some use here as it does give us the relations: $x = 4 + 5i; ~ x = -1 + 25j; ~ x = -1+125k$, where $x = 2^{1150} mod 5^6$. All these relations can be easily generated without any need for a calculator (I did it within 2 minutes). You just need Euler's theorem, know basic properties of the totient function and possess elementary knowledge of group theory, especially group generators and the related tests.
$endgroup$
– Novice Geek
Jan 23 at 15:14
1
1
$begingroup$
I wouldn't say Euler's theorem is impossible to use. But it doesn't help much, no.
$endgroup$
– Arthur
Jan 23 at 13:26
$begingroup$
I wouldn't say Euler's theorem is impossible to use. But it doesn't help much, no.
$endgroup$
– Arthur
Jan 23 at 13:26
3
3
$begingroup$
Perhaps $$2^{1150}=(5-1)^{575}equiv-1+binom{575}{1}5-binom{575}{2}5^2+binom{575}{3}5^3pmod{5^6}$$ may be helpful...?
$endgroup$
– Sangchul Lee
Jan 23 at 13:31
$begingroup$
Perhaps $$2^{1150}=(5-1)^{575}equiv-1+binom{575}{1}5-binom{575}{2}5^2+binom{575}{3}5^3pmod{5^6}$$ may be helpful...?
$endgroup$
– Sangchul Lee
Jan 23 at 13:31
$begingroup$
@SangchulLee What happened to $binom{575}45^4$ and $binom{575}55^5$?
$endgroup$
– Arthur
Jan 23 at 13:33
$begingroup$
@SangchulLee What happened to $binom{575}45^4$ and $binom{575}55^5$?
$endgroup$
– Arthur
Jan 23 at 13:33
1
1
$begingroup$
@Arthur, I utilized $575=5^2times23$, which shows $5^2midbinom{575}{4}$ and $5midbinom{575}{5}$
$endgroup$
– Sangchul Lee
Jan 23 at 13:34
$begingroup$
@Arthur, I utilized $575=5^2times23$, which shows $5^2midbinom{575}{4}$ and $5midbinom{575}{5}$
$endgroup$
– Sangchul Lee
Jan 23 at 13:34
$begingroup$
Well, Euler's Th. can be of some use here as it does give us the relations: $x = 4 + 5i; ~ x = -1 + 25j; ~ x = -1+125k$, where $x = 2^{1150} mod 5^6$. All these relations can be easily generated without any need for a calculator (I did it within 2 minutes). You just need Euler's theorem, know basic properties of the totient function and possess elementary knowledge of group theory, especially group generators and the related tests.
$endgroup$
– Novice Geek
Jan 23 at 15:14
$begingroup$
Well, Euler's Th. can be of some use here as it does give us the relations: $x = 4 + 5i; ~ x = -1 + 25j; ~ x = -1+125k$, where $x = 2^{1150} mod 5^6$. All these relations can be easily generated without any need for a calculator (I did it within 2 minutes). You just need Euler's theorem, know basic properties of the totient function and possess elementary knowledge of group theory, especially group generators and the related tests.
$endgroup$
– Novice Geek
Jan 23 at 15:14
add a comment |
0
active
oldest
votes
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
});
}
});
draft saved
draft discarded
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%2f3084463%2fmodulo-computing-without-eulers-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3084463%2fmodulo-computing-without-eulers-theorem%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$
I wouldn't say Euler's theorem is impossible to use. But it doesn't help much, no.
$endgroup$
– Arthur
Jan 23 at 13:26
3
$begingroup$
Perhaps $$2^{1150}=(5-1)^{575}equiv-1+binom{575}{1}5-binom{575}{2}5^2+binom{575}{3}5^3pmod{5^6}$$ may be helpful...?
$endgroup$
– Sangchul Lee
Jan 23 at 13:31
$begingroup$
@SangchulLee What happened to $binom{575}45^4$ and $binom{575}55^5$?
$endgroup$
– Arthur
Jan 23 at 13:33
1
$begingroup$
@Arthur, I utilized $575=5^2times23$, which shows $5^2midbinom{575}{4}$ and $5midbinom{575}{5}$
$endgroup$
– Sangchul Lee
Jan 23 at 13:34
$begingroup$
Well, Euler's Th. can be of some use here as it does give us the relations: $x = 4 + 5i; ~ x = -1 + 25j; ~ x = -1+125k$, where $x = 2^{1150} mod 5^6$. All these relations can be easily generated without any need for a calculator (I did it within 2 minutes). You just need Euler's theorem, know basic properties of the totient function and possess elementary knowledge of group theory, especially group generators and the related tests.
$endgroup$
– Novice Geek
Jan 23 at 15:14