Trying to find a modulo for $2^{24}$
$begingroup$
I was trying to figure out which modulo n would satisfy that $2^{24}$ is congruent to 1 mod n. One answer is 241, and I wonder if there is a good way to find it.
I tried to use Fermat's little theorem or Chinese Remainder theorem,but 24 is not a prime and 241 is not composite.
modular-arithmetic
asked Nov 28 '18 at 17:10
Jingting931015Jingting931015
828
$endgroup$
add a comment |
$begingroup$
I was trying to figure out which modulo n would satisfy that $2^{24}$ is congruent to 1 mod n. One answer is 241, and I wonder if there is a good way to find it.
I tried to use Fermat's little theorem or Chinese Remainder theorem,but 24 is not a prime and 241 is not composite.
modular-arithmetic
asked Nov 28 '18 at 17:10
Jingting931015Jingting931015
828
$endgroup$
add a comment |
$begingroup$
I was trying to figure out which modulo n would satisfy that $2^{24}$ is congruent to 1 mod n. One answer is 241, and I wonder if there is a good way to find it.
I tried to use Fermat's little theorem or Chinese Remainder theorem,but 24 is not a prime and 241 is not composite.
modular-arithmetic
asked Nov 28 '18 at 17:10
Jingting931015Jingting931015
828
$endgroup$
I was trying to figure out which modulo n would satisfy that $2^{24}$ is congruent to 1 mod n. One answer is 241, and I wonder if there is a good way to find it.
I tried to use Fermat's little theorem or Chinese Remainder theorem,but 24 is not a prime and 241 is not composite.
modular-arithmetic
modular-arithmetic
asked Nov 28 '18 at 17:10
Jingting931015Jingting931015
828
asked Nov 28 '18 at 17:10
Jingting931015Jingting931015
828
edited Nov 28 '18 at 17:18
Jingting931015
asked Nov 28 '18 at 17:10
Jingting931015Jingting931015
828
asked Nov 28 '18 at 17:10
Jingting931015Jingting931015
828
asked Nov 28 '18 at 17:10
Jingting931015Jingting931015
828
828
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Direct factoring gives:
$$2^{24}-1=(2^{12}-1)(2^{12}+1)=(2^6-1)(2^6+1)(2^{12}+1)=(2^3-1)(2^3+1)(2^6+1)(2^{12}+1)$$
So: $2^3-1=7$ will work (as will $3$ or any of the factors of $2^6+1$ or $2^{12}+1$).
Indeed, a little effort shows that the full list of primes that work here is ${3,5,7, 13,17, 241}$
answered Nov 28 '18 at 17:14
lulululu
40.7k24879
$endgroup$
add a comment |
$begingroup$
We want to find factors of
begin{align}(2^{24}-1)&=(2^{12}-1)(2^{12}+1)\
&= (2^6-1)(2^6+1)(2^{12}+1)
end{align}
Hence we can for example, pick our $n$ to be $2^6-1, 2^6+1$ or $2^{12}+1$. Notice that $241$ is a factor of $2^{12}+1$.
Also note that $$2^{24}=(2^3)^8=(7+1)^8$$
Hence we can pick $n=7$.
Also $$2^{24}=(2^8)^3=((2^8-1)+1)^3$$
Hence, we can pick $n=2^8-1$ or its factors and so on.
answered Nov 28 '18 at 17:14
Siong Thye GohSiong Thye Goh
101k1466117
$endgroup$
add a comment |
$begingroup$
the simplest is to find an odd prime $p$ such that $p-1$ is a divisor of $24$. You have at once:
$$p= 3, 5, 7,13.$$
You also have chances it works with a prime $p$ such that a divisor of $24$ ($>1$) is also a divisor of $p-1$. For instance $17$ works ($2$ has order $8$ modulo $17$).
answered Nov 28 '18 at 17:39
BernardBernard
120k740113
$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%2f3017405%2ftrying-to-find-a-modulo-for-224%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$
Direct factoring gives:
$$2^{24}-1=(2^{12}-1)(2^{12}+1)=(2^6-1)(2^6+1)(2^{12}+1)=(2^3-1)(2^3+1)(2^6+1)(2^{12}+1)$$
So: $2^3-1=7$ will work (as will $3$ or any of the factors of $2^6+1$ or $2^{12}+1$).
Indeed, a little effort shows that the full list of primes that work here is ${3,5,7, 13,17, 241}$
answered Nov 28 '18 at 17:14
lulululu
40.7k24879
$endgroup$
add a comment |
$begingroup$
Direct factoring gives:
$$2^{24}-1=(2^{12}-1)(2^{12}+1)=(2^6-1)(2^6+1)(2^{12}+1)=(2^3-1)(2^3+1)(2^6+1)(2^{12}+1)$$
So: $2^3-1=7$ will work (as will $3$ or any of the factors of $2^6+1$ or $2^{12}+1$).
Indeed, a little effort shows that the full list of primes that work here is ${3,5,7, 13,17, 241}$
answered Nov 28 '18 at 17:14
lulululu
40.7k24879
$endgroup$
add a comment |
$begingroup$
Direct factoring gives:
$$2^{24}-1=(2^{12}-1)(2^{12}+1)=(2^6-1)(2^6+1)(2^{12}+1)=(2^3-1)(2^3+1)(2^6+1)(2^{12}+1)$$
So: $2^3-1=7$ will work (as will $3$ or any of the factors of $2^6+1$ or $2^{12}+1$).
Indeed, a little effort shows that the full list of primes that work here is ${3,5,7, 13,17, 241}$
answered Nov 28 '18 at 17:14
lulululu
40.7k24879
$endgroup$
Direct factoring gives:
$$2^{24}-1=(2^{12}-1)(2^{12}+1)=(2^6-1)(2^6+1)(2^{12}+1)=(2^3-1)(2^3+1)(2^6+1)(2^{12}+1)$$
So: $2^3-1=7$ will work (as will $3$ or any of the factors of $2^6+1$ or $2^{12}+1$).
Indeed, a little effort shows that the full list of primes that work here is ${3,5,7, 13,17, 241}$
answered Nov 28 '18 at 17:14
lulululu
40.7k24879
answered Nov 28 '18 at 17:14
lulululu
40.7k24879
answered Nov 28 '18 at 17:14
lulululu
40.7k24879
answered Nov 28 '18 at 17:14
lulululu
40.7k24879
40.7k24879
add a comment |
add a comment |
$begingroup$
We want to find factors of
begin{align}(2^{24}-1)&=(2^{12}-1)(2^{12}+1)\
&= (2^6-1)(2^6+1)(2^{12}+1)
end{align}
Hence we can for example, pick our $n$ to be $2^6-1, 2^6+1$ or $2^{12}+1$. Notice that $241$ is a factor of $2^{12}+1$.
Also note that $$2^{24}=(2^3)^8=(7+1)^8$$
Hence we can pick $n=7$.
Also $$2^{24}=(2^8)^3=((2^8-1)+1)^3$$
Hence, we can pick $n=2^8-1$ or its factors and so on.
answered Nov 28 '18 at 17:14
Siong Thye GohSiong Thye Goh
101k1466117
$endgroup$
add a comment |
$begingroup$
We want to find factors of
begin{align}(2^{24}-1)&=(2^{12}-1)(2^{12}+1)\
&= (2^6-1)(2^6+1)(2^{12}+1)
end{align}
Hence we can for example, pick our $n$ to be $2^6-1, 2^6+1$ or $2^{12}+1$. Notice that $241$ is a factor of $2^{12}+1$.
Also note that $$2^{24}=(2^3)^8=(7+1)^8$$
Hence we can pick $n=7$.
Also $$2^{24}=(2^8)^3=((2^8-1)+1)^3$$
Hence, we can pick $n=2^8-1$ or its factors and so on.
answered Nov 28 '18 at 17:14
Siong Thye GohSiong Thye Goh
101k1466117
$endgroup$
add a comment |
$begingroup$
We want to find factors of
begin{align}(2^{24}-1)&=(2^{12}-1)(2^{12}+1)\
&= (2^6-1)(2^6+1)(2^{12}+1)
end{align}
Hence we can for example, pick our $n$ to be $2^6-1, 2^6+1$ or $2^{12}+1$. Notice that $241$ is a factor of $2^{12}+1$.
Also note that $$2^{24}=(2^3)^8=(7+1)^8$$
Hence we can pick $n=7$.
Also $$2^{24}=(2^8)^3=((2^8-1)+1)^3$$
Hence, we can pick $n=2^8-1$ or its factors and so on.
answered Nov 28 '18 at 17:14
Siong Thye GohSiong Thye Goh
101k1466117
$endgroup$
We want to find factors of
begin{align}(2^{24}-1)&=(2^{12}-1)(2^{12}+1)\
&= (2^6-1)(2^6+1)(2^{12}+1)
end{align}
Hence we can for example, pick our $n$ to be $2^6-1, 2^6+1$ or $2^{12}+1$. Notice that $241$ is a factor of $2^{12}+1$.
Also note that $$2^{24}=(2^3)^8=(7+1)^8$$
Hence we can pick $n=7$.
Also $$2^{24}=(2^8)^3=((2^8-1)+1)^3$$
Hence, we can pick $n=2^8-1$ or its factors and so on.
answered Nov 28 '18 at 17:14
Siong Thye GohSiong Thye Goh
101k1466117
edited Nov 28 '18 at 17:22
answered Nov 28 '18 at 17:14
Siong Thye GohSiong Thye Goh
101k1466117
answered Nov 28 '18 at 17:14
Siong Thye GohSiong Thye Goh
101k1466117
answered Nov 28 '18 at 17:14
Siong Thye GohSiong Thye Goh
101k1466117
101k1466117
add a comment |
add a comment |
$begingroup$
the simplest is to find an odd prime $p$ such that $p-1$ is a divisor of $24$. You have at once:
$$p= 3, 5, 7,13.$$
You also have chances it works with a prime $p$ such that a divisor of $24$ ($>1$) is also a divisor of $p-1$. For instance $17$ works ($2$ has order $8$ modulo $17$).
answered Nov 28 '18 at 17:39
BernardBernard
120k740113
$endgroup$
add a comment |
$begingroup$
the simplest is to find an odd prime $p$ such that $p-1$ is a divisor of $24$. You have at once:
$$p= 3, 5, 7,13.$$
You also have chances it works with a prime $p$ such that a divisor of $24$ ($>1$) is also a divisor of $p-1$. For instance $17$ works ($2$ has order $8$ modulo $17$).
answered Nov 28 '18 at 17:39
BernardBernard
120k740113
$endgroup$
add a comment |
$begingroup$
the simplest is to find an odd prime $p$ such that $p-1$ is a divisor of $24$. You have at once:
$$p= 3, 5, 7,13.$$
You also have chances it works with a prime $p$ such that a divisor of $24$ ($>1$) is also a divisor of $p-1$. For instance $17$ works ($2$ has order $8$ modulo $17$).
answered Nov 28 '18 at 17:39
BernardBernard
120k740113
$endgroup$
the simplest is to find an odd prime $p$ such that $p-1$ is a divisor of $24$. You have at once:
$$p= 3, 5, 7,13.$$
You also have chances it works with a prime $p$ such that a divisor of $24$ ($>1$) is also a divisor of $p-1$. For instance $17$ works ($2$ has order $8$ modulo $17$).
answered Nov 28 '18 at 17:39
BernardBernard
120k740113
answered Nov 28 '18 at 17:39
BernardBernard
120k740113
answered Nov 28 '18 at 17:39
BernardBernard
120k740113
answered Nov 28 '18 at 17:39
BernardBernard
120k740113
120k740113
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%2f3017405%2ftrying-to-find-a-modulo-for-224%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
