Is there a $n$ that $3^{3n}-1$ is divisible by 16.
up vote
-3
down vote
favorite
Is there a $n$ that $3^{3n}-1$ is divisible by 16?
(excuse me for the previous careless question)
elementary-number-theory
add a comment |
up vote
-3
down vote
favorite
Is there a $n$ that $3^{3n}-1$ is divisible by 16?
(excuse me for the previous careless question)
elementary-number-theory
1
Sure, $n=4$ will do.
– the_fox
Nov 28 at 22:08
1
$n=4$ or $n=8$.
– hamam_Abdallah
Nov 28 at 22:08
2
How many times are you going to ask variations on this question? Can you please try to decide what exactly you're curious about before posting a question?
– Arthur
Nov 28 at 22:12
add a comment |
up vote
-3
down vote
favorite
up vote
-3
down vote
favorite
Is there a $n$ that $3^{3n}-1$ is divisible by 16?
(excuse me for the previous careless question)
elementary-number-theory
Is there a $n$ that $3^{3n}-1$ is divisible by 16?
(excuse me for the previous careless question)
elementary-number-theory
elementary-number-theory
asked Nov 28 at 22:03
user620772
1
Sure, $n=4$ will do.
– the_fox
Nov 28 at 22:08
1
$n=4$ or $n=8$.
– hamam_Abdallah
Nov 28 at 22:08
2
How many times are you going to ask variations on this question? Can you please try to decide what exactly you're curious about before posting a question?
– Arthur
Nov 28 at 22:12
add a comment |
1
Sure, $n=4$ will do.
– the_fox
Nov 28 at 22:08
1
$n=4$ or $n=8$.
– hamam_Abdallah
Nov 28 at 22:08
2
How many times are you going to ask variations on this question? Can you please try to decide what exactly you're curious about before posting a question?
– Arthur
Nov 28 at 22:12
1
1
Sure, $n=4$ will do.
– the_fox
Nov 28 at 22:08
Sure, $n=4$ will do.
– the_fox
Nov 28 at 22:08
1
1
$n=4$ or $n=8$.
– hamam_Abdallah
Nov 28 at 22:08
$n=4$ or $n=8$.
– hamam_Abdallah
Nov 28 at 22:08
2
2
How many times are you going to ask variations on this question? Can you please try to decide what exactly you're curious about before posting a question?
– Arthur
Nov 28 at 22:12
How many times are you going to ask variations on this question? Can you please try to decide what exactly you're curious about before posting a question?
– Arthur
Nov 28 at 22:12
add a comment |
7 Answers
7
active
oldest
votes
up vote
1
down vote
By Carmichael's function, if $lcd(a,m)=1$ and $a,m,kinmathbb N$ $$a^{lambda(m)·k}equiv1mod{m}$$
In this example, since 3 and 16 are coprime $$3^{lambda(16)·k}equiv 1 mod{16}$$
$$Rightarrow 3^{4k}-1equiv0mod{16}$$
Thus, for any $ninmathbb{N}$ such that $4mid(3n)$, $3^{3n}-1$ is divisible by 16.
Hence $forall nin{xinmathbb N:4mid x}$, i.e., whenever $n$ is a multiple of 4, the condition is satisfied
answered Nov 28 at 22:18
Dr. Mathva
928315
add a comment |
up vote
1
down vote
hint
$$3^{3n}-1=(3^n)^3-1^3$$
$$=(3^n-1)(3^{2n}+3^n+1)$$
we just need $3^n-1$ to be divisible by $16$.
let us look for even $n=2p$.
then
$$3^n-1=(3^p+1)(3^p-1)$$
$3^p+1$ is even. we need $3^p-1$ divisible by $8$. we take $p=2$.
it gives $n=4$.
answered Nov 28 at 22:11
hamam_Abdallah
37.7k21634
add a comment |
up vote
0
down vote
Yes; $n=4$ gives $3^{3n}-1=531440$, which is divisible by 16.
answered Nov 28 at 22:07
Benedict Randall Shaw
50610
add a comment |
up vote
0
down vote
We rewrite this as a request to seek $n$ such that $1 equiv 3^{3n} = 27^n equiv (-5)^n mod 16.$
By repeated squaring, $n = 4$ works.
answered Nov 28 at 22:08
Display name
789313
add a comment |
up vote
0
down vote
$3^{3n}-1=27^n-1=(27-1)(27^{n-1}+27^{n-2}+ldots+1)$, so if $16|3^{3n}-1,$ then $8|(27^{n-1}+27^{n-2}+ldots+1)$, since $2|26$. This can then be solved by trial and error, or possibly other methods
answered Nov 28 at 22:09
Seth
43612
add a comment |
up vote
0
down vote
We need to do little more than render $3^4=81=5×16+1$. Thereby, $16|(3^4-1)$ and then $(a-1)|(a^3-1)$ for all whole numbers $a$ other than $1$. By the transitive property, $16|((3^4)^3-1)=3^{3×4}-1$.
answered Nov 28 at 22:14
Oscar Lanzi
12k12036
add a comment |
up vote
0
down vote
Yes. $3^3 = 27 equiv 11$ mod 16 and, as 11 is prime, 11 is an element of the group $left(mathbb{Z}/16mathbb{Z}right)^{times}$. Thus there is some integer $n'$ such that $11^{n'} equiv_{16} 1$ and the smallest such integer $n'$ is less than 16 and in fact $n'$ divides $|left(mathbb{Z}/16mathbb{Z}right)^{times}| = 8$ [make sure you see why]. Furthermore for every other integer $k$, the equation $11^{kn'} equiv_{16} 1$ holds [make sure you see why]. Thus for each $n$ of the form $n=kn'$; $k$ and $n'$ as before, the integer $27^{n}-1$ is a multiple of 16 [make sure you see why]
answered Nov 28 at 22:11
Mike
2,804211
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%2f3017790%2fis-there-a-n-that-33n-1-is-divisible-by-16%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
7 Answers
7
active
oldest
votes
7 Answers
7
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
By Carmichael's function, if $lcd(a,m)=1$ and $a,m,kinmathbb N$ $$a^{lambda(m)·k}equiv1mod{m}$$
In this example, since 3 and 16 are coprime $$3^{lambda(16)·k}equiv 1 mod{16}$$
$$Rightarrow 3^{4k}-1equiv0mod{16}$$
Thus, for any $ninmathbb{N}$ such that $4mid(3n)$, $3^{3n}-1$ is divisible by 16.
Hence $forall nin{xinmathbb N:4mid x}$, i.e., whenever $n$ is a multiple of 4, the condition is satisfied
answered Nov 28 at 22:18
Dr. Mathva
928315
add a comment |
up vote
1
down vote
By Carmichael's function, if $lcd(a,m)=1$ and $a,m,kinmathbb N$ $$a^{lambda(m)·k}equiv1mod{m}$$
In this example, since 3 and 16 are coprime $$3^{lambda(16)·k}equiv 1 mod{16}$$
$$Rightarrow 3^{4k}-1equiv0mod{16}$$
Thus, for any $ninmathbb{N}$ such that $4mid(3n)$, $3^{3n}-1$ is divisible by 16.
Hence $forall nin{xinmathbb N:4mid x}$, i.e., whenever $n$ is a multiple of 4, the condition is satisfied
answered Nov 28 at 22:18
Dr. Mathva
928315
add a comment |
up vote
1
down vote
up vote
1
down vote
By Carmichael's function, if $lcd(a,m)=1$ and $a,m,kinmathbb N$ $$a^{lambda(m)·k}equiv1mod{m}$$
In this example, since 3 and 16 are coprime $$3^{lambda(16)·k}equiv 1 mod{16}$$
$$Rightarrow 3^{4k}-1equiv0mod{16}$$
Thus, for any $ninmathbb{N}$ such that $4mid(3n)$, $3^{3n}-1$ is divisible by 16.
Hence $forall nin{xinmathbb N:4mid x}$, i.e., whenever $n$ is a multiple of 4, the condition is satisfied
answered Nov 28 at 22:18
Dr. Mathva
928315
By Carmichael's function, if $lcd(a,m)=1$ and $a,m,kinmathbb N$ $$a^{lambda(m)·k}equiv1mod{m}$$
In this example, since 3 and 16 are coprime $$3^{lambda(16)·k}equiv 1 mod{16}$$
$$Rightarrow 3^{4k}-1equiv0mod{16}$$
Thus, for any $ninmathbb{N}$ such that $4mid(3n)$, $3^{3n}-1$ is divisible by 16.
Hence $forall nin{xinmathbb N:4mid x}$, i.e., whenever $n$ is a multiple of 4, the condition is satisfied
answered Nov 28 at 22:18
Dr. Mathva
928315
answered Nov 28 at 22:18
Dr. Mathva
928315
answered Nov 28 at 22:18
Dr. Mathva
928315
answered Nov 28 at 22:18
Dr. Mathva
928315
928315
add a comment |
add a comment |
up vote
1
down vote
hint
$$3^{3n}-1=(3^n)^3-1^3$$
$$=(3^n-1)(3^{2n}+3^n+1)$$
we just need $3^n-1$ to be divisible by $16$.
let us look for even $n=2p$.
then
$$3^n-1=(3^p+1)(3^p-1)$$
$3^p+1$ is even. we need $3^p-1$ divisible by $8$. we take $p=2$.
it gives $n=4$.
answered Nov 28 at 22:11
hamam_Abdallah
37.7k21634
add a comment |
up vote
1
down vote
hint
$$3^{3n}-1=(3^n)^3-1^3$$
$$=(3^n-1)(3^{2n}+3^n+1)$$
we just need $3^n-1$ to be divisible by $16$.
let us look for even $n=2p$.
then
$$3^n-1=(3^p+1)(3^p-1)$$
$3^p+1$ is even. we need $3^p-1$ divisible by $8$. we take $p=2$.
it gives $n=4$.
answered Nov 28 at 22:11
hamam_Abdallah
37.7k21634
add a comment |
up vote
1
down vote
up vote
1
down vote
hint
$$3^{3n}-1=(3^n)^3-1^3$$
$$=(3^n-1)(3^{2n}+3^n+1)$$
we just need $3^n-1$ to be divisible by $16$.
let us look for even $n=2p$.
then
$$3^n-1=(3^p+1)(3^p-1)$$
$3^p+1$ is even. we need $3^p-1$ divisible by $8$. we take $p=2$.
it gives $n=4$.
answered Nov 28 at 22:11
hamam_Abdallah
37.7k21634
hint
$$3^{3n}-1=(3^n)^3-1^3$$
$$=(3^n-1)(3^{2n}+3^n+1)$$
we just need $3^n-1$ to be divisible by $16$.
let us look for even $n=2p$.
then
$$3^n-1=(3^p+1)(3^p-1)$$
$3^p+1$ is even. we need $3^p-1$ divisible by $8$. we take $p=2$.
it gives $n=4$.
answered Nov 28 at 22:11
hamam_Abdallah
37.7k21634
edited Nov 29 at 19:31
answered Nov 28 at 22:11
hamam_Abdallah
37.7k21634
answered Nov 28 at 22:11
hamam_Abdallah
37.7k21634
answered Nov 28 at 22:11
hamam_Abdallah
37.7k21634
37.7k21634
add a comment |
add a comment |
up vote
0
down vote
Yes; $n=4$ gives $3^{3n}-1=531440$, which is divisible by 16.
answered Nov 28 at 22:07
Benedict Randall Shaw
50610
add a comment |
up vote
0
down vote
Yes; $n=4$ gives $3^{3n}-1=531440$, which is divisible by 16.
answered Nov 28 at 22:07
Benedict Randall Shaw
50610
add a comment |
up vote
0
down vote
up vote
0
down vote
Yes; $n=4$ gives $3^{3n}-1=531440$, which is divisible by 16.
answered Nov 28 at 22:07
Benedict Randall Shaw
50610
Yes; $n=4$ gives $3^{3n}-1=531440$, which is divisible by 16.
answered Nov 28 at 22:07
Benedict Randall Shaw
50610
answered Nov 28 at 22:07
Benedict Randall Shaw
50610
answered Nov 28 at 22:07
Benedict Randall Shaw
50610
answered Nov 28 at 22:07
Benedict Randall Shaw
50610
50610
add a comment |
add a comment |
up vote
0
down vote
We rewrite this as a request to seek $n$ such that $1 equiv 3^{3n} = 27^n equiv (-5)^n mod 16.$
By repeated squaring, $n = 4$ works.
answered Nov 28 at 22:08
Display name
789313
add a comment |
up vote
0
down vote
We rewrite this as a request to seek $n$ such that $1 equiv 3^{3n} = 27^n equiv (-5)^n mod 16.$
By repeated squaring, $n = 4$ works.
answered Nov 28 at 22:08
Display name
789313
add a comment |
up vote
0
down vote
up vote
0
down vote
We rewrite this as a request to seek $n$ such that $1 equiv 3^{3n} = 27^n equiv (-5)^n mod 16.$
By repeated squaring, $n = 4$ works.
answered Nov 28 at 22:08
Display name
789313
We rewrite this as a request to seek $n$ such that $1 equiv 3^{3n} = 27^n equiv (-5)^n mod 16.$
By repeated squaring, $n = 4$ works.
answered Nov 28 at 22:08
Display name
789313
answered Nov 28 at 22:08
Display name
789313
answered Nov 28 at 22:08
Display name
789313
answered Nov 28 at 22:08
Display name
789313
789313
add a comment |
add a comment |
up vote
0
down vote
$3^{3n}-1=27^n-1=(27-1)(27^{n-1}+27^{n-2}+ldots+1)$, so if $16|3^{3n}-1,$ then $8|(27^{n-1}+27^{n-2}+ldots+1)$, since $2|26$. This can then be solved by trial and error, or possibly other methods
answered Nov 28 at 22:09
Seth
43612
add a comment |
up vote
0
down vote
$3^{3n}-1=27^n-1=(27-1)(27^{n-1}+27^{n-2}+ldots+1)$, so if $16|3^{3n}-1,$ then $8|(27^{n-1}+27^{n-2}+ldots+1)$, since $2|26$. This can then be solved by trial and error, or possibly other methods
answered Nov 28 at 22:09
Seth
43612
add a comment |
up vote
0
down vote
up vote
0
down vote
$3^{3n}-1=27^n-1=(27-1)(27^{n-1}+27^{n-2}+ldots+1)$, so if $16|3^{3n}-1,$ then $8|(27^{n-1}+27^{n-2}+ldots+1)$, since $2|26$. This can then be solved by trial and error, or possibly other methods
answered Nov 28 at 22:09
Seth
43612
$3^{3n}-1=27^n-1=(27-1)(27^{n-1}+27^{n-2}+ldots+1)$, so if $16|3^{3n}-1,$ then $8|(27^{n-1}+27^{n-2}+ldots+1)$, since $2|26$. This can then be solved by trial and error, or possibly other methods
answered Nov 28 at 22:09
Seth
43612
answered Nov 28 at 22:09
Seth
43612
answered Nov 28 at 22:09
Seth
43612
answered Nov 28 at 22:09
Seth
43612
43612
add a comment |
add a comment |
up vote
0
down vote
We need to do little more than render $3^4=81=5×16+1$. Thereby, $16|(3^4-1)$ and then $(a-1)|(a^3-1)$ for all whole numbers $a$ other than $1$. By the transitive property, $16|((3^4)^3-1)=3^{3×4}-1$.
answered Nov 28 at 22:14
Oscar Lanzi
12k12036
add a comment |
up vote
0
down vote
We need to do little more than render $3^4=81=5×16+1$. Thereby, $16|(3^4-1)$ and then $(a-1)|(a^3-1)$ for all whole numbers $a$ other than $1$. By the transitive property, $16|((3^4)^3-1)=3^{3×4}-1$.
answered Nov 28 at 22:14
Oscar Lanzi
12k12036
add a comment |
up vote
0
down vote
up vote
0
down vote
We need to do little more than render $3^4=81=5×16+1$. Thereby, $16|(3^4-1)$ and then $(a-1)|(a^3-1)$ for all whole numbers $a$ other than $1$. By the transitive property, $16|((3^4)^3-1)=3^{3×4}-1$.
answered Nov 28 at 22:14
Oscar Lanzi
12k12036
We need to do little more than render $3^4=81=5×16+1$. Thereby, $16|(3^4-1)$ and then $(a-1)|(a^3-1)$ for all whole numbers $a$ other than $1$. By the transitive property, $16|((3^4)^3-1)=3^{3×4}-1$.
answered Nov 28 at 22:14
Oscar Lanzi
12k12036
answered Nov 28 at 22:14
Oscar Lanzi
12k12036
answered Nov 28 at 22:14
Oscar Lanzi
12k12036
answered Nov 28 at 22:14
Oscar Lanzi
12k12036
12k12036
add a comment |
add a comment |
up vote
0
down vote
Yes. $3^3 = 27 equiv 11$ mod 16 and, as 11 is prime, 11 is an element of the group $left(mathbb{Z}/16mathbb{Z}right)^{times}$. Thus there is some integer $n'$ such that $11^{n'} equiv_{16} 1$ and the smallest such integer $n'$ is less than 16 and in fact $n'$ divides $|left(mathbb{Z}/16mathbb{Z}right)^{times}| = 8$ [make sure you see why]. Furthermore for every other integer $k$, the equation $11^{kn'} equiv_{16} 1$ holds [make sure you see why]. Thus for each $n$ of the form $n=kn'$; $k$ and $n'$ as before, the integer $27^{n}-1$ is a multiple of 16 [make sure you see why]
answered Nov 28 at 22:11
Mike
2,804211
add a comment |
up vote
0
down vote
Yes. $3^3 = 27 equiv 11$ mod 16 and, as 11 is prime, 11 is an element of the group $left(mathbb{Z}/16mathbb{Z}right)^{times}$. Thus there is some integer $n'$ such that $11^{n'} equiv_{16} 1$ and the smallest such integer $n'$ is less than 16 and in fact $n'$ divides $|left(mathbb{Z}/16mathbb{Z}right)^{times}| = 8$ [make sure you see why]. Furthermore for every other integer $k$, the equation $11^{kn'} equiv_{16} 1$ holds [make sure you see why]. Thus for each $n$ of the form $n=kn'$; $k$ and $n'$ as before, the integer $27^{n}-1$ is a multiple of 16 [make sure you see why]
answered Nov 28 at 22:11
Mike
2,804211
add a comment |
up vote
0
down vote
up vote
0
down vote
Yes. $3^3 = 27 equiv 11$ mod 16 and, as 11 is prime, 11 is an element of the group $left(mathbb{Z}/16mathbb{Z}right)^{times}$. Thus there is some integer $n'$ such that $11^{n'} equiv_{16} 1$ and the smallest such integer $n'$ is less than 16 and in fact $n'$ divides $|left(mathbb{Z}/16mathbb{Z}right)^{times}| = 8$ [make sure you see why]. Furthermore for every other integer $k$, the equation $11^{kn'} equiv_{16} 1$ holds [make sure you see why]. Thus for each $n$ of the form $n=kn'$; $k$ and $n'$ as before, the integer $27^{n}-1$ is a multiple of 16 [make sure you see why]
answered Nov 28 at 22:11
Mike
2,804211
Yes. $3^3 = 27 equiv 11$ mod 16 and, as 11 is prime, 11 is an element of the group $left(mathbb{Z}/16mathbb{Z}right)^{times}$. Thus there is some integer $n'$ such that $11^{n'} equiv_{16} 1$ and the smallest such integer $n'$ is less than 16 and in fact $n'$ divides $|left(mathbb{Z}/16mathbb{Z}right)^{times}| = 8$ [make sure you see why]. Furthermore for every other integer $k$, the equation $11^{kn'} equiv_{16} 1$ holds [make sure you see why]. Thus for each $n$ of the form $n=kn'$; $k$ and $n'$ as before, the integer $27^{n}-1$ is a multiple of 16 [make sure you see why]
answered Nov 28 at 22:11
Mike
2,804211
edited Nov 28 at 22:17
answered Nov 28 at 22:11
Mike
2,804211
answered Nov 28 at 22:11
Mike
2,804211
answered Nov 28 at 22:11
Mike
2,804211
2,804211
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3017790%2fis-there-a-n-that-33n-1-is-divisible-by-16%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
Sure, $n=4$ will do.
– the_fox
Nov 28 at 22:08
1
$n=4$ or $n=8$.
– hamam_Abdallah
Nov 28 at 22:08
2
How many times are you going to ask variations on this question? Can you please try to decide what exactly you're curious about before posting a question?
– Arthur
Nov 28 at 22:12