Mixing
Show that $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$
$begingroup$
I was checking the following Fermat's little theorem exercise:
Show that $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$
I've started by stating each congruence individually suposing that each $n,6n$ and $4n$ are primes with $11$, for the first one I have:
$$n^{10} equiv 1 mod {11}$$
$$ equiv n^{3} mod {11}$$
I've stated the second one this way
$$6n^{10} equiv 1 mod {11}$$
But honestly I don't know how to go ahead as long as I don't have a number to evaluate with $11$.
Also I'm considering that I have:
$$n + 6n + 4n = 11n$$
This may have some relation with the proof but could be affected because of the powers of each one. Any help will be really appreciated.
number-theory modular-arithmetic
asked Jan 28 at 6:03
mrazmraz
44319
$endgroup$
add a comment |
$begingroup$
I was checking the following Fermat's little theorem exercise:
Show that $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$
I've started by stating each congruence individually suposing that each $n,6n$ and $4n$ are primes with $11$, for the first one I have:
$$n^{10} equiv 1 mod {11}$$
$$ equiv n^{3} mod {11}$$
I've stated the second one this way
$$6n^{10} equiv 1 mod {11}$$
But honestly I don't know how to go ahead as long as I don't have a number to evaluate with $11$.
Also I'm considering that I have:
$$n + 6n + 4n = 11n$$
This may have some relation with the proof but could be affected because of the powers of each one. Any help will be really appreciated.
number-theory modular-arithmetic
asked Jan 28 at 6:03
mrazmraz
44319
$endgroup$
add a comment |
$begingroup$
I was checking the following Fermat's little theorem exercise:
Show that $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$
I've started by stating each congruence individually suposing that each $n,6n$ and $4n$ are primes with $11$, for the first one I have:
$$n^{10} equiv 1 mod {11}$$
$$ equiv n^{3} mod {11}$$
I've stated the second one this way
$$6n^{10} equiv 1 mod {11}$$
But honestly I don't know how to go ahead as long as I don't have a number to evaluate with $11$.
Also I'm considering that I have:
$$n + 6n + 4n = 11n$$
This may have some relation with the proof but could be affected because of the powers of each one. Any help will be really appreciated.
number-theory modular-arithmetic
asked Jan 28 at 6:03
mrazmraz
44319
$endgroup$
I was checking the following Fermat's little theorem exercise:
Show that $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$
I've started by stating each congruence individually suposing that each $n,6n$ and $4n$ are primes with $11$, for the first one I have:
$$n^{10} equiv 1 mod {11}$$
$$ equiv n^{3} mod {11}$$
I've stated the second one this way
$$6n^{10} equiv 1 mod {11}$$
But honestly I don't know how to go ahead as long as I don't have a number to evaluate with $11$.
Also I'm considering that I have:
$$n + 6n + 4n = 11n$$
This may have some relation with the proof but could be affected because of the powers of each one. Any help will be really appreciated.
number-theory modular-arithmetic
number-theory modular-arithmetic
asked Jan 28 at 6:03
mrazmraz
44319
asked Jan 28 at 6:03
mrazmraz
44319
asked Jan 28 at 6:03
mrazmraz
44319
asked Jan 28 at 6:03
mrazmraz
44319
asked Jan 28 at 6:03
mrazmraz
44319
44319
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
From what you shown, we have $$n^{10} equiv n^{20} equiv 1 mod 11$$ and thus $$n^{23} equiv n^3 mod 11$$
We also have $$n^{10} equiv 1 mod 11$$ and thus we have $$6n^{13} equiv 6n^3 mod 11$$
Lastly, we have that the last term is: $$4n^3 mod 11$$
Adding it all up, we have that this is equivalent to $$n^{23} + 6n^{13} + 4n^3 equiv n^3 + 6n^3 + 4n^3 equiv 0 mod 11$$
answered Jan 28 at 6:09
twnlytwnly
1,2011214
$endgroup$
add a comment |
$begingroup$
Fermat's little theorem only applies when prime $p$ does not divide $a$ in $a^{p-1} equiv 1 pmod p$.
In your expression, if $n$ is a multiple of $11$ the theorem doesn't apply but the expression is trivially a multiple of $11$.
If $n$ is not a multiple of $11$ the theorem applies. Now note:
$n^{10} equiv 1 pmod{11}$
$n^{20} equiv 1^2 = 1 pmod {11}$
So modulo $11$, your expression reduces to $n^3 + 6n^3 + 4n^3 =11n^3$, which is clearly a multiple of $11$.
answered Jan 28 at 6:12
DeepakDeepak
17.5k11539
$endgroup$
add a comment |
$begingroup$
$$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3(mod11)$$
By Fermat's little thoerem, $n^{10}equiv1(mod 11)$ since 11 is prime.
Therefore $$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3equiv11n^3equiv0(mod 11)$$
answered Jan 28 at 6:10
abc...abc...
3,237739
$endgroup$
add a comment |
$begingroup$
You almost have it. By Fermat's theorem $n^{10}equiv 1 mod11 $ when $gcd(n,11)=1$ so
$$n^{23},n^{13},n^3equiv n^3 mod11$$
$$n^{23}+6n^{13}+4n^{3}equiv 11n^3mod11 $$ The result is obvious if $n$ is a multple of $11$. Hence $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$ for all $n$.
answered Jan 28 at 6:10
Yadati KiranYadati Kiran
2,1101622
$endgroup$
add a comment |
$begingroup$
It all comes down to Fermat's little theorem in the end. Here is another way of proceeding, which is sometimes handy when there isn't an easy or obvious way forward. We work modulo $11$ and note that $11$ is prime, so it divides a product if it divides one of the factors.
$$n^{23}+6n^{13}+4n^3equiv n^3left(n^{20}-5n^{10}+4right)equiv n^3left(n^{10}-1right)left(n^{10}-4right)$$
[Adjusting the coefficients by multiples of $11$ to get an easy factorisation is the trick, and if it works it can make life somewhat easier]
And if the expression is divisible by $11$ one of the factors must be. And this indicates where to look. One danger here is that factorising further to obtain factors $(n^5pm 1)$ and $(n^5pm 2)$ doesn't help much.
answered Jan 28 at 7:01
Mark BennetMark Bennet
81.8k984183
$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%2f3090530%2fshow-that-n236n134n3-is-a-multiple-of-11%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
From what you shown, we have $$n^{10} equiv n^{20} equiv 1 mod 11$$ and thus $$n^{23} equiv n^3 mod 11$$
We also have $$n^{10} equiv 1 mod 11$$ and thus we have $$6n^{13} equiv 6n^3 mod 11$$
Lastly, we have that the last term is: $$4n^3 mod 11$$
Adding it all up, we have that this is equivalent to $$n^{23} + 6n^{13} + 4n^3 equiv n^3 + 6n^3 + 4n^3 equiv 0 mod 11$$
answered Jan 28 at 6:09
twnlytwnly
1,2011214
$endgroup$
add a comment |
$begingroup$
From what you shown, we have $$n^{10} equiv n^{20} equiv 1 mod 11$$ and thus $$n^{23} equiv n^3 mod 11$$
We also have $$n^{10} equiv 1 mod 11$$ and thus we have $$6n^{13} equiv 6n^3 mod 11$$
Lastly, we have that the last term is: $$4n^3 mod 11$$
Adding it all up, we have that this is equivalent to $$n^{23} + 6n^{13} + 4n^3 equiv n^3 + 6n^3 + 4n^3 equiv 0 mod 11$$
answered Jan 28 at 6:09
twnlytwnly
1,2011214
$endgroup$
add a comment |
$begingroup$
From what you shown, we have $$n^{10} equiv n^{20} equiv 1 mod 11$$ and thus $$n^{23} equiv n^3 mod 11$$
We also have $$n^{10} equiv 1 mod 11$$ and thus we have $$6n^{13} equiv 6n^3 mod 11$$
Lastly, we have that the last term is: $$4n^3 mod 11$$
Adding it all up, we have that this is equivalent to $$n^{23} + 6n^{13} + 4n^3 equiv n^3 + 6n^3 + 4n^3 equiv 0 mod 11$$
answered Jan 28 at 6:09
twnlytwnly
1,2011214
$endgroup$
From what you shown, we have $$n^{10} equiv n^{20} equiv 1 mod 11$$ and thus $$n^{23} equiv n^3 mod 11$$
We also have $$n^{10} equiv 1 mod 11$$ and thus we have $$6n^{13} equiv 6n^3 mod 11$$
Lastly, we have that the last term is: $$4n^3 mod 11$$
Adding it all up, we have that this is equivalent to $$n^{23} + 6n^{13} + 4n^3 equiv n^3 + 6n^3 + 4n^3 equiv 0 mod 11$$
answered Jan 28 at 6:09
twnlytwnly
1,2011214
answered Jan 28 at 6:09
twnlytwnly
1,2011214
answered Jan 28 at 6:09
twnlytwnly
1,2011214
answered Jan 28 at 6:09
twnlytwnly
1,2011214
1,2011214
add a comment |
add a comment |
$begingroup$
Fermat's little theorem only applies when prime $p$ does not divide $a$ in $a^{p-1} equiv 1 pmod p$.
In your expression, if $n$ is a multiple of $11$ the theorem doesn't apply but the expression is trivially a multiple of $11$.
If $n$ is not a multiple of $11$ the theorem applies. Now note:
$n^{10} equiv 1 pmod{11}$
$n^{20} equiv 1^2 = 1 pmod {11}$
So modulo $11$, your expression reduces to $n^3 + 6n^3 + 4n^3 =11n^3$, which is clearly a multiple of $11$.
answered Jan 28 at 6:12
DeepakDeepak
17.5k11539
$endgroup$
add a comment |
$begingroup$
Fermat's little theorem only applies when prime $p$ does not divide $a$ in $a^{p-1} equiv 1 pmod p$.
In your expression, if $n$ is a multiple of $11$ the theorem doesn't apply but the expression is trivially a multiple of $11$.
If $n$ is not a multiple of $11$ the theorem applies. Now note:
$n^{10} equiv 1 pmod{11}$
$n^{20} equiv 1^2 = 1 pmod {11}$
So modulo $11$, your expression reduces to $n^3 + 6n^3 + 4n^3 =11n^3$, which is clearly a multiple of $11$.
answered Jan 28 at 6:12
DeepakDeepak
17.5k11539
$endgroup$
add a comment |
$begingroup$
Fermat's little theorem only applies when prime $p$ does not divide $a$ in $a^{p-1} equiv 1 pmod p$.
In your expression, if $n$ is a multiple of $11$ the theorem doesn't apply but the expression is trivially a multiple of $11$.
If $n$ is not a multiple of $11$ the theorem applies. Now note:
$n^{10} equiv 1 pmod{11}$
$n^{20} equiv 1^2 = 1 pmod {11}$
So modulo $11$, your expression reduces to $n^3 + 6n^3 + 4n^3 =11n^3$, which is clearly a multiple of $11$.
answered Jan 28 at 6:12
DeepakDeepak
17.5k11539
$endgroup$
Fermat's little theorem only applies when prime $p$ does not divide $a$ in $a^{p-1} equiv 1 pmod p$.
In your expression, if $n$ is a multiple of $11$ the theorem doesn't apply but the expression is trivially a multiple of $11$.
If $n$ is not a multiple of $11$ the theorem applies. Now note:
$n^{10} equiv 1 pmod{11}$
$n^{20} equiv 1^2 = 1 pmod {11}$
So modulo $11$, your expression reduces to $n^3 + 6n^3 + 4n^3 =11n^3$, which is clearly a multiple of $11$.
answered Jan 28 at 6:12
DeepakDeepak
17.5k11539
answered Jan 28 at 6:12
DeepakDeepak
17.5k11539
answered Jan 28 at 6:12
DeepakDeepak
17.5k11539
answered Jan 28 at 6:12
DeepakDeepak
17.5k11539
17.5k11539
add a comment |
add a comment |
$begingroup$
$$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3(mod11)$$
By Fermat's little thoerem, $n^{10}equiv1(mod 11)$ since 11 is prime.
Therefore $$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3equiv11n^3equiv0(mod 11)$$
answered Jan 28 at 6:10
abc...abc...
3,237739
$endgroup$
add a comment |
$begingroup$
$$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3(mod11)$$
By Fermat's little thoerem, $n^{10}equiv1(mod 11)$ since 11 is prime.
Therefore $$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3equiv11n^3equiv0(mod 11)$$
answered Jan 28 at 6:10
abc...abc...
3,237739
$endgroup$
add a comment |
$begingroup$
$$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3(mod11)$$
By Fermat's little thoerem, $n^{10}equiv1(mod 11)$ since 11 is prime.
Therefore $$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3equiv11n^3equiv0(mod 11)$$
answered Jan 28 at 6:10
abc...abc...
3,237739
$endgroup$
$$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3(mod11)$$
By Fermat's little thoerem, $n^{10}equiv1(mod 11)$ since 11 is prime.
Therefore $$n^{23}+6n^{13}+4n^3equiv n^3 *n^{20}+6n^3*n^{10}+4n^3equiv11n^3equiv0(mod 11)$$
answered Jan 28 at 6:10
abc...abc...
3,237739
answered Jan 28 at 6:10
abc...abc...
3,237739
answered Jan 28 at 6:10
abc...abc...
3,237739
answered Jan 28 at 6:10
abc...abc...
3,237739
3,237739
add a comment |
add a comment |
$begingroup$
You almost have it. By Fermat's theorem $n^{10}equiv 1 mod11 $ when $gcd(n,11)=1$ so
$$n^{23},n^{13},n^3equiv n^3 mod11$$
$$n^{23}+6n^{13}+4n^{3}equiv 11n^3mod11 $$ The result is obvious if $n$ is a multple of $11$. Hence $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$ for all $n$.
answered Jan 28 at 6:10
Yadati KiranYadati Kiran
2,1101622
$endgroup$
add a comment |
$begingroup$
You almost have it. By Fermat's theorem $n^{10}equiv 1 mod11 $ when $gcd(n,11)=1$ so
$$n^{23},n^{13},n^3equiv n^3 mod11$$
$$n^{23}+6n^{13}+4n^{3}equiv 11n^3mod11 $$ The result is obvious if $n$ is a multple of $11$. Hence $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$ for all $n$.
answered Jan 28 at 6:10
Yadati KiranYadati Kiran
2,1101622
$endgroup$
add a comment |
$begingroup$
You almost have it. By Fermat's theorem $n^{10}equiv 1 mod11 $ when $gcd(n,11)=1$ so
$$n^{23},n^{13},n^3equiv n^3 mod11$$
$$n^{23}+6n^{13}+4n^{3}equiv 11n^3mod11 $$ The result is obvious if $n$ is a multple of $11$. Hence $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$ for all $n$.
answered Jan 28 at 6:10
Yadati KiranYadati Kiran
2,1101622
$endgroup$
You almost have it. By Fermat's theorem $n^{10}equiv 1 mod11 $ when $gcd(n,11)=1$ so
$$n^{23},n^{13},n^3equiv n^3 mod11$$
$$n^{23}+6n^{13}+4n^{3}equiv 11n^3mod11 $$ The result is obvious if $n$ is a multple of $11$. Hence $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$ for all $n$.
answered Jan 28 at 6:10
Yadati KiranYadati Kiran
2,1101622
edited Jan 28 at 6:23
answered Jan 28 at 6:10
Yadati KiranYadati Kiran
2,1101622
answered Jan 28 at 6:10
Yadati KiranYadati Kiran
2,1101622
answered Jan 28 at 6:10
Yadati KiranYadati Kiran
2,1101622
2,1101622
add a comment |
add a comment |
$begingroup$
It all comes down to Fermat's little theorem in the end. Here is another way of proceeding, which is sometimes handy when there isn't an easy or obvious way forward. We work modulo $11$ and note that $11$ is prime, so it divides a product if it divides one of the factors.
$$n^{23}+6n^{13}+4n^3equiv n^3left(n^{20}-5n^{10}+4right)equiv n^3left(n^{10}-1right)left(n^{10}-4right)$$
[Adjusting the coefficients by multiples of $11$ to get an easy factorisation is the trick, and if it works it can make life somewhat easier]
And if the expression is divisible by $11$ one of the factors must be. And this indicates where to look. One danger here is that factorising further to obtain factors $(n^5pm 1)$ and $(n^5pm 2)$ doesn't help much.
answered Jan 28 at 7:01
Mark BennetMark Bennet
81.8k984183
$endgroup$
add a comment |
$begingroup$
It all comes down to Fermat's little theorem in the end. Here is another way of proceeding, which is sometimes handy when there isn't an easy or obvious way forward. We work modulo $11$ and note that $11$ is prime, so it divides a product if it divides one of the factors.
$$n^{23}+6n^{13}+4n^3equiv n^3left(n^{20}-5n^{10}+4right)equiv n^3left(n^{10}-1right)left(n^{10}-4right)$$
[Adjusting the coefficients by multiples of $11$ to get an easy factorisation is the trick, and if it works it can make life somewhat easier]
And if the expression is divisible by $11$ one of the factors must be. And this indicates where to look. One danger here is that factorising further to obtain factors $(n^5pm 1)$ and $(n^5pm 2)$ doesn't help much.
answered Jan 28 at 7:01
Mark BennetMark Bennet
81.8k984183
$endgroup$
add a comment |
$begingroup$
It all comes down to Fermat's little theorem in the end. Here is another way of proceeding, which is sometimes handy when there isn't an easy or obvious way forward. We work modulo $11$ and note that $11$ is prime, so it divides a product if it divides one of the factors.
$$n^{23}+6n^{13}+4n^3equiv n^3left(n^{20}-5n^{10}+4right)equiv n^3left(n^{10}-1right)left(n^{10}-4right)$$
[Adjusting the coefficients by multiples of $11$ to get an easy factorisation is the trick, and if it works it can make life somewhat easier]
And if the expression is divisible by $11$ one of the factors must be. And this indicates where to look. One danger here is that factorising further to obtain factors $(n^5pm 1)$ and $(n^5pm 2)$ doesn't help much.
answered Jan 28 at 7:01
Mark BennetMark Bennet
81.8k984183
$endgroup$
It all comes down to Fermat's little theorem in the end. Here is another way of proceeding, which is sometimes handy when there isn't an easy or obvious way forward. We work modulo $11$ and note that $11$ is prime, so it divides a product if it divides one of the factors.
$$n^{23}+6n^{13}+4n^3equiv n^3left(n^{20}-5n^{10}+4right)equiv n^3left(n^{10}-1right)left(n^{10}-4right)$$
[Adjusting the coefficients by multiples of $11$ to get an easy factorisation is the trick, and if it works it can make life somewhat easier]
And if the expression is divisible by $11$ one of the factors must be. And this indicates where to look. One danger here is that factorising further to obtain factors $(n^5pm 1)$ and $(n^5pm 2)$ doesn't help much.
answered Jan 28 at 7:01
Mark BennetMark Bennet
81.8k984183
answered Jan 28 at 7:01
Mark BennetMark Bennet
81.8k984183
answered Jan 28 at 7:01
Mark BennetMark Bennet
81.8k984183
answered Jan 28 at 7:01
Mark BennetMark Bennet
81.8k984183
81.8k984183
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%2f3090530%2fshow-that-n236n134n3-is-a-multiple-of-11%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
