Mixing
How to show that $2730mid n^{13}-n;;forall ninmathbb{N}$
$begingroup$
Show that $2730mid n^{13}-n,;;forall ninmathbb{N}$
I tried, $2730=13cdot5cdot7cdot3cdot2$
We have $13mid n^{13}-n$, by Fermat's Little Theorem.
We have $2mid n^{13}-n$, by if $n$ even then $n^{13}-n$ too is even; if $n$ is odd $n^{13}-n$ is odd.
And the numbers $5$ and $7$, how to proceed?
elementary-number-theory divisibility totient-function
edited Aug 7 '15 at 10:21
Jyrki Lahtonen
110k13172387
asked Dec 6 '13 at 21:09
marcelolpjuniormarcelolpjunior
1,99031743
$endgroup$
add a comment |
$begingroup$
Show that $2730mid n^{13}-n,;;forall ninmathbb{N}$
I tried, $2730=13cdot5cdot7cdot3cdot2$
We have $13mid n^{13}-n$, by Fermat's Little Theorem.
We have $2mid n^{13}-n$, by if $n$ even then $n^{13}-n$ too is even; if $n$ is odd $n^{13}-n$ is odd.
And the numbers $5$ and $7$, how to proceed?
elementary-number-theory divisibility totient-function
edited Aug 7 '15 at 10:21
Jyrki Lahtonen
110k13172387
asked Dec 6 '13 at 21:09
marcelolpjuniormarcelolpjunior
1,99031743
$endgroup$
1
$begingroup$
It seems like a factorization of $n^{13}-n$ should do it.
$endgroup$
– user99680
Dec 6 '13 at 21:12
$begingroup$
See also math.stackexchange.com/questions/1387239/…
$endgroup$
– Martin Sleziak
Aug 7 '15 at 10:03
$begingroup$
By FLT $5|n^5 - n$ , $7|n^7 - n$ and $3|n^3 - n$. $n^13 - n = n(n^12 - 1) = n(n^6 + 1)(n^6 - 1) = n(n^6+1)(n^3 + 1)(n^3 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n^2 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n+1) (n-1)$. $n^7 - n = n(n^6 - 1)$ is a factor. $n^3 -n = n(n^2 - 1)$ is a factor. 5? well if $n = i mod 5$ if i = 0 5|n if i = 1 5|n - 1. If i = 4 5|n+1. If i = 2 or 3 5|n^6+1.
$endgroup$
– fleablood
Jul 5 '16 at 19:33
add a comment |
$begingroup$
Show that $2730mid n^{13}-n,;;forall ninmathbb{N}$
I tried, $2730=13cdot5cdot7cdot3cdot2$
We have $13mid n^{13}-n$, by Fermat's Little Theorem.
We have $2mid n^{13}-n$, by if $n$ even then $n^{13}-n$ too is even; if $n$ is odd $n^{13}-n$ is odd.
And the numbers $5$ and $7$, how to proceed?
elementary-number-theory divisibility totient-function
edited Aug 7 '15 at 10:21
Jyrki Lahtonen
110k13172387
asked Dec 6 '13 at 21:09
marcelolpjuniormarcelolpjunior
1,99031743
$endgroup$
Show that $2730mid n^{13}-n,;;forall ninmathbb{N}$
I tried, $2730=13cdot5cdot7cdot3cdot2$
We have $13mid n^{13}-n$, by Fermat's Little Theorem.
We have $2mid n^{13}-n$, by if $n$ even then $n^{13}-n$ too is even; if $n$ is odd $n^{13}-n$ is odd.
And the numbers $5$ and $7$, how to proceed?
elementary-number-theory divisibility totient-function
elementary-number-theory divisibility totient-function
edited Aug 7 '15 at 10:21
Jyrki Lahtonen
110k13172387
asked Dec 6 '13 at 21:09
marcelolpjuniormarcelolpjunior
1,99031743
edited Aug 7 '15 at 10:21
Jyrki Lahtonen
110k13172387
asked Dec 6 '13 at 21:09
marcelolpjuniormarcelolpjunior
1,99031743
edited Aug 7 '15 at 10:21
Jyrki Lahtonen
110k13172387
edited Aug 7 '15 at 10:21
Jyrki Lahtonen
110k13172387
edited Aug 7 '15 at 10:21
Jyrki Lahtonen
110k13172387
110k13172387
asked Dec 6 '13 at 21:09
marcelolpjuniormarcelolpjunior
1,99031743
asked Dec 6 '13 at 21:09
marcelolpjuniormarcelolpjunior
1,99031743
asked Dec 6 '13 at 21:09
marcelolpjuniormarcelolpjunior
1,99031743
1,99031743
1
$begingroup$
It seems like a factorization of $n^{13}-n$ should do it.
$endgroup$
– user99680
Dec 6 '13 at 21:12
$begingroup$
See also math.stackexchange.com/questions/1387239/…
$endgroup$
– Martin Sleziak
Aug 7 '15 at 10:03
$begingroup$
By FLT $5|n^5 - n$ , $7|n^7 - n$ and $3|n^3 - n$. $n^13 - n = n(n^12 - 1) = n(n^6 + 1)(n^6 - 1) = n(n^6+1)(n^3 + 1)(n^3 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n^2 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n+1) (n-1)$. $n^7 - n = n(n^6 - 1)$ is a factor. $n^3 -n = n(n^2 - 1)$ is a factor. 5? well if $n = i mod 5$ if i = 0 5|n if i = 1 5|n - 1. If i = 4 5|n+1. If i = 2 or 3 5|n^6+1.
$endgroup$
– fleablood
Jul 5 '16 at 19:33
add a comment |
1
$begingroup$
It seems like a factorization of $n^{13}-n$ should do it.
$endgroup$
– user99680
Dec 6 '13 at 21:12
$begingroup$
See also math.stackexchange.com/questions/1387239/…
$endgroup$
– Martin Sleziak
Aug 7 '15 at 10:03
$begingroup$
By FLT $5|n^5 - n$ , $7|n^7 - n$ and $3|n^3 - n$. $n^13 - n = n(n^12 - 1) = n(n^6 + 1)(n^6 - 1) = n(n^6+1)(n^3 + 1)(n^3 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n^2 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n+1) (n-1)$. $n^7 - n = n(n^6 - 1)$ is a factor. $n^3 -n = n(n^2 - 1)$ is a factor. 5? well if $n = i mod 5$ if i = 0 5|n if i = 1 5|n - 1. If i = 4 5|n+1. If i = 2 or 3 5|n^6+1.
$endgroup$
– fleablood
Jul 5 '16 at 19:33
1
1
$begingroup$
It seems like a factorization of $n^{13}-n$ should do it.
$endgroup$
– user99680
Dec 6 '13 at 21:12
$begingroup$
It seems like a factorization of $n^{13}-n$ should do it.
$endgroup$
– user99680
Dec 6 '13 at 21:12
$begingroup$
See also math.stackexchange.com/questions/1387239/…
$endgroup$
– Martin Sleziak
Aug 7 '15 at 10:03
$begingroup$
See also math.stackexchange.com/questions/1387239/…
$endgroup$
– Martin Sleziak
Aug 7 '15 at 10:03
$begingroup$
By FLT $5|n^5 - n$ , $7|n^7 - n$ and $3|n^3 - n$. $n^13 - n = n(n^12 - 1) = n(n^6 + 1)(n^6 - 1) = n(n^6+1)(n^3 + 1)(n^3 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n^2 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n+1) (n-1)$. $n^7 - n = n(n^6 - 1)$ is a factor. $n^3 -n = n(n^2 - 1)$ is a factor. 5? well if $n = i mod 5$ if i = 0 5|n if i = 1 5|n - 1. If i = 4 5|n+1. If i = 2 or 3 5|n^6+1.
$endgroup$
– fleablood
Jul 5 '16 at 19:33
$begingroup$
By FLT $5|n^5 - n$ , $7|n^7 - n$ and $3|n^3 - n$. $n^13 - n = n(n^12 - 1) = n(n^6 + 1)(n^6 - 1) = n(n^6+1)(n^3 + 1)(n^3 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n^2 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n+1) (n-1)$. $n^7 - n = n(n^6 - 1)$ is a factor. $n^3 -n = n(n^2 - 1)$ is a factor. 5? well if $n = i mod 5$ if i = 0 5|n if i = 1 5|n - 1. If i = 4 5|n+1. If i = 2 or 3 5|n^6+1.
$endgroup$
– fleablood
Jul 5 '16 at 19:33
add a comment |
10 Answers
10
active
oldest
votes
$begingroup$
Like user99680,
Using Fermat's Little Theorem $p|(n^p-n)$ where $n$ is any integer and $p$ is any prime
$displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^6)^2-1right)=n(n^6-1)(n^6+1)=(n^7-n)(n^6+1)$ which is divisible by $displaystyle n^7-n$ which is always divisible by $7$ for all integer $n$
Similarly, $displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^4)^3-1right)$
$displaystyle=n(n^4-1)(n^8+n^4+1)=(n^5-n)(n^8+n^4+1)$ which is divisible by $displaystyle n^5-n$ which is always divisible by $5$ for all integer $n$
edited Aug 7 '15 at 11:09
vonbrand
20k63260
answered Dec 7 '13 at 5:26
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
$begingroup$
You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$
$endgroup$
– PM 2Ring
Aug 7 '15 at 10:29
add a comment |
$begingroup$
HINT:
$$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5$$
$$n^{13} equiv n^6 cdot n^7 equiv n pmod 7$$
Also you've missed $3$ as prime factor. But that should be easy.
answered Dec 6 '13 at 21:15
Stefan4024Stefan4024
30.6k63579
$endgroup$
add a comment |
$begingroup$
One Approach
If $kmid n$, then $x^{k+1}-xmid x^{n+1}-x$. Therefore,
$$
begin{array}{}
13&mid&n^{13}-n\
7&mid&n^7-n&mid&n^{13}-n&text{since }6mid12\
5&mid&n^5-n&mid&n^{13}-n&text{since }4mid12\
3&mid&n^3-n&mid&n^{13}-n&text{since }2mid12\
2&mid&n^2-n&mid&n^{13}-n&text{since }1mid12\
end{array}
$$
Since the factors are all relatively prime, we have that
$$
2730=2cdot3cdot5cdot7cdot 13mid n^{13}-n
$$
Another Approach
Decomposing into a sum of combinatorial polynomials
$$
begin{align}
n^{13}-n
&=2730left[vphantom{binom{n}{2}}right.3binom{n}{2}+575binom{n}{3}+22264binom{n}{4}+330044binom{n}{5}\
&+2458368binom{n}{6}+10551552binom{n}{7}+28055808binom{n}{8}+47786112binom{n}{9}\
&+52272000binom{n}{10}+35544960binom{n}{11}+13685760binom{n}{12}+2280960binom{n}{13}left.vphantom{binom{n}{2}}right]\
end{align}
$$
answered Aug 7 '15 at 11:05
robjohn♦robjohn
270k27312640
$endgroup$
3
$begingroup$
Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it.
$endgroup$
– Lubin
Aug 7 '15 at 12:06
$begingroup$
Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $binom{n}{0}$. Evaluating $n^{13}-n-c_0binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $binom{n}{1}$. Evaluating $n^{13}-n-c_0binom{n}{0}-c_1binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $binom{n}{2}$. etc. Other than the large numbers, it is pretty simple.
$endgroup$
– robjohn♦
Aug 7 '15 at 12:34
add a comment |
$begingroup$
Notice that $n^{13}-n =n(n^{12}-1)=n(n^6+1)(n^6-1)=n(n^6+1)(n^3+1)(n^3-1)=...$
answered Dec 6 '13 at 21:14
user99680user99680
5,972821
$endgroup$
add a comment |
$begingroup$
Note that $$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5 equiv n^{13} equiv n^6 cdot n^7 equiv n pmod 7.$$
answered Dec 6 '13 at 21:16
Ahaan S. RungtaAhaan S. Rungta
6,53352161
$endgroup$
add a comment |
$begingroup$
$, n = 2730 = 2cdot 3cdot 5cdot 7cdot 13 = ,$ product of all primes $rm ,p,$ such that $rm color{#c00}{p!-!1mid 13!-!1}.,$ Now apply
Theorem $ $ For natural numbers $rm:a,e,n:$ with $rm:e,n>1$
$qquadrm n:|:a^{large e}-a:$ for all $rm:a:iff n:$ is squarefree, and prime $rm:p:|:n,Rightarrow, color{#c00}{p!-!1mid e!-!1}$
Proof $ $ See this answer for a short simple proof.
answered Jul 5 '16 at 19:16
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
add a comment |
$begingroup$
$2730 = 2cdot 3cdot 5cdot 7cdot 13$
The Carmichael function or least universal exponent function is composed by least common multiple over prime components, so $lambda(2730) = text{lcm}(lambda(2), lambda(3), lambda(5), lambda(7), lambda(13)) = text{lcm}(1,2,4,6,12)=12$. Note also that $2730$ is square-free, so the exponent cycle will be entered by the first power ($n^1$) for all numbers. Of course numbers coprime to $2730$ enter the cycle at the zeroth power ($1$).
Thus(!) $n^{(1+12)}equiv n^1 bmod 2730$ as required.
answered Dec 21 '17 at 19:55
JoffanJoffan
32.6k43269
$endgroup$
add a comment |
$begingroup$
Cute corollary to FLT.
If $p,q $ are primes and $p-1=m|q-1=k$ then
$p|n^p -n=n (n^m-1)|n (n^m-1)(n^{k-m} + n^{k - 2m}+...+n^m+1)=n (n^k-1)=n^q-n $.
So as $1,2,3,4,6,12$ all divide $12$, it follows $2,3,5,7,13$ all divide $n^{13}- n $.
For me personally it was hardest to see that 5 did but $n^{13}-n = (n^8 + n^4 + 1)(n^5- n) $ so ... it does.
answered Jul 5 '16 at 19:53
fleabloodfleablood
73.6k22891
$endgroup$
add a comment |
$begingroup$
You can find the Chinese remainder theorem very useful.
answered Dec 6 '13 at 21:15
randuserranduser
42838
$endgroup$
add a comment |
$begingroup$
Here is some way of automating Rob John's method:
You can always use decomposition over polynomials :$quaddisplaystyle Pi_k(n)=k!binom nk=prodlimits_{i=0}^{k-1} (n-i)$
e.g. $ Pi_4(n)=(n-3)(n-2)(n-1)n$
To solve problems of the type: "show $m$ divides the polynomial $P(n)$"
Let have a look at a simpler example using this technique :
Prove $(n^5-n)$ is divisible by 5 by induction.
Though for $n^{13}-n$ it is a bit tedious.
Here is a maple procedure to do it:
> binomexpansion :=proc(P)
local a,b,c,d,i,p,q:
p:=P: d:= degree(P):
printf("%a = ",P):
for i from d to 0 by -1 do
a:=coeff(p,n,i):
q:=expand(binomial(n,i)):
b:=coeff(q,n,i):
c:=a/b:
p:=p-c*q:
if((c>0)and(i<d)) then printf("+"); fi:
if(c<>0) then printf("%d(n,%d)",c,i); fi:
end do: printf("n"):
end proc
> binomexpansion(n^13-n);
n^13-n = 6227020800(n,13)+37362124800(n,12)+97037740800(n,11)+142702560000(n,10)+
130456085760(n,9)+76592355840(n,8)+28805736960(n,7)+6711344640(n,6)+
901020120(n,5)+60780720(n,4)+1569750(n,3)+8190(n,2)
You can notice that all coefficients are divisible by $2730=2.3.5.7.13$.
And since the binomial coefficients are integers, you get the divisibility by $2730$ as a result.
answered Feb 27 at 20:46
zwimzwim
12.6k831
$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%2f596074%2fhow-to-show-that-2730-mid-n13-n-forall-n-in-mathbbn%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Like user99680,
Using Fermat's Little Theorem $p|(n^p-n)$ where $n$ is any integer and $p$ is any prime
$displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^6)^2-1right)=n(n^6-1)(n^6+1)=(n^7-n)(n^6+1)$ which is divisible by $displaystyle n^7-n$ which is always divisible by $7$ for all integer $n$
Similarly, $displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^4)^3-1right)$
$displaystyle=n(n^4-1)(n^8+n^4+1)=(n^5-n)(n^8+n^4+1)$ which is divisible by $displaystyle n^5-n$ which is always divisible by $5$ for all integer $n$
edited Aug 7 '15 at 11:09
vonbrand
20k63260
answered Dec 7 '13 at 5:26
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
$begingroup$
You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$
$endgroup$
– PM 2Ring
Aug 7 '15 at 10:29
add a comment |
$begingroup$
Like user99680,
Using Fermat's Little Theorem $p|(n^p-n)$ where $n$ is any integer and $p$ is any prime
$displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^6)^2-1right)=n(n^6-1)(n^6+1)=(n^7-n)(n^6+1)$ which is divisible by $displaystyle n^7-n$ which is always divisible by $7$ for all integer $n$
Similarly, $displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^4)^3-1right)$
$displaystyle=n(n^4-1)(n^8+n^4+1)=(n^5-n)(n^8+n^4+1)$ which is divisible by $displaystyle n^5-n$ which is always divisible by $5$ for all integer $n$
edited Aug 7 '15 at 11:09
vonbrand
20k63260
answered Dec 7 '13 at 5:26
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
$begingroup$
You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$
$endgroup$
– PM 2Ring
Aug 7 '15 at 10:29
add a comment |
$begingroup$
Like user99680,
Using Fermat's Little Theorem $p|(n^p-n)$ where $n$ is any integer and $p$ is any prime
$displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^6)^2-1right)=n(n^6-1)(n^6+1)=(n^7-n)(n^6+1)$ which is divisible by $displaystyle n^7-n$ which is always divisible by $7$ for all integer $n$
Similarly, $displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^4)^3-1right)$
$displaystyle=n(n^4-1)(n^8+n^4+1)=(n^5-n)(n^8+n^4+1)$ which is divisible by $displaystyle n^5-n$ which is always divisible by $5$ for all integer $n$
edited Aug 7 '15 at 11:09
vonbrand
20k63260
answered Dec 7 '13 at 5:26
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
Like user99680,
Using Fermat's Little Theorem $p|(n^p-n)$ where $n$ is any integer and $p$ is any prime
$displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^6)^2-1right)=n(n^6-1)(n^6+1)=(n^7-n)(n^6+1)$ which is divisible by $displaystyle n^7-n$ which is always divisible by $7$ for all integer $n$
Similarly, $displaystyle n^{13}-n=n(n^{12}-1)=nleft((n^4)^3-1right)$
$displaystyle=n(n^4-1)(n^8+n^4+1)=(n^5-n)(n^8+n^4+1)$ which is divisible by $displaystyle n^5-n$ which is always divisible by $5$ for all integer $n$
edited Aug 7 '15 at 11:09
vonbrand
20k63260
answered Dec 7 '13 at 5:26
lab bhattacharjeelab bhattacharjee
228k15158279
edited Aug 7 '15 at 11:09
vonbrand
20k63260
edited Aug 7 '15 at 11:09
vonbrand
20k63260
edited Aug 7 '15 at 11:09
vonbrand
20k63260
20k63260
answered Dec 7 '13 at 5:26
lab bhattacharjeelab bhattacharjee
228k15158279
answered Dec 7 '13 at 5:26
lab bhattacharjeelab bhattacharjee
228k15158279
answered Dec 7 '13 at 5:26
lab bhattacharjeelab bhattacharjee
228k15158279
228k15158279
$begingroup$
You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$
$endgroup$
– PM 2Ring
Aug 7 '15 at 10:29
add a comment |
$begingroup$
You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$
$endgroup$
– PM 2Ring
Aug 7 '15 at 10:29
$begingroup$
You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$
$endgroup$
– PM 2Ring
Aug 7 '15 at 10:29
$begingroup$
You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$
$endgroup$
– PM 2Ring
Aug 7 '15 at 10:29
add a comment |
$begingroup$
HINT:
$$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5$$
$$n^{13} equiv n^6 cdot n^7 equiv n pmod 7$$
Also you've missed $3$ as prime factor. But that should be easy.
answered Dec 6 '13 at 21:15
Stefan4024Stefan4024
30.6k63579
$endgroup$
add a comment |
$begingroup$
HINT:
$$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5$$
$$n^{13} equiv n^6 cdot n^7 equiv n pmod 7$$
Also you've missed $3$ as prime factor. But that should be easy.
answered Dec 6 '13 at 21:15
Stefan4024Stefan4024
30.6k63579
$endgroup$
add a comment |
$begingroup$
HINT:
$$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5$$
$$n^{13} equiv n^6 cdot n^7 equiv n pmod 7$$
Also you've missed $3$ as prime factor. But that should be easy.
answered Dec 6 '13 at 21:15
Stefan4024Stefan4024
30.6k63579
$endgroup$
HINT:
$$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5$$
$$n^{13} equiv n^6 cdot n^7 equiv n pmod 7$$
Also you've missed $3$ as prime factor. But that should be easy.
answered Dec 6 '13 at 21:15
Stefan4024Stefan4024
30.6k63579
answered Dec 6 '13 at 21:15
Stefan4024Stefan4024
30.6k63579
answered Dec 6 '13 at 21:15
Stefan4024Stefan4024
30.6k63579
answered Dec 6 '13 at 21:15
Stefan4024Stefan4024
30.6k63579
30.6k63579
add a comment |
add a comment |
$begingroup$
One Approach
If $kmid n$, then $x^{k+1}-xmid x^{n+1}-x$. Therefore,
$$
begin{array}{}
13&mid&n^{13}-n\
7&mid&n^7-n&mid&n^{13}-n&text{since }6mid12\
5&mid&n^5-n&mid&n^{13}-n&text{since }4mid12\
3&mid&n^3-n&mid&n^{13}-n&text{since }2mid12\
2&mid&n^2-n&mid&n^{13}-n&text{since }1mid12\
end{array}
$$
Since the factors are all relatively prime, we have that
$$
2730=2cdot3cdot5cdot7cdot 13mid n^{13}-n
$$
Another Approach
Decomposing into a sum of combinatorial polynomials
$$
begin{align}
n^{13}-n
&=2730left[vphantom{binom{n}{2}}right.3binom{n}{2}+575binom{n}{3}+22264binom{n}{4}+330044binom{n}{5}\
&+2458368binom{n}{6}+10551552binom{n}{7}+28055808binom{n}{8}+47786112binom{n}{9}\
&+52272000binom{n}{10}+35544960binom{n}{11}+13685760binom{n}{12}+2280960binom{n}{13}left.vphantom{binom{n}{2}}right]\
end{align}
$$
answered Aug 7 '15 at 11:05
robjohn♦robjohn
270k27312640
$endgroup$
3
$begingroup$
Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it.
$endgroup$
– Lubin
Aug 7 '15 at 12:06
$begingroup$
Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $binom{n}{0}$. Evaluating $n^{13}-n-c_0binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $binom{n}{1}$. Evaluating $n^{13}-n-c_0binom{n}{0}-c_1binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $binom{n}{2}$. etc. Other than the large numbers, it is pretty simple.
$endgroup$
– robjohn♦
Aug 7 '15 at 12:34
add a comment |
$begingroup$
One Approach
If $kmid n$, then $x^{k+1}-xmid x^{n+1}-x$. Therefore,
$$
begin{array}{}
13&mid&n^{13}-n\
7&mid&n^7-n&mid&n^{13}-n&text{since }6mid12\
5&mid&n^5-n&mid&n^{13}-n&text{since }4mid12\
3&mid&n^3-n&mid&n^{13}-n&text{since }2mid12\
2&mid&n^2-n&mid&n^{13}-n&text{since }1mid12\
end{array}
$$
Since the factors are all relatively prime, we have that
$$
2730=2cdot3cdot5cdot7cdot 13mid n^{13}-n
$$
Another Approach
Decomposing into a sum of combinatorial polynomials
$$
begin{align}
n^{13}-n
&=2730left[vphantom{binom{n}{2}}right.3binom{n}{2}+575binom{n}{3}+22264binom{n}{4}+330044binom{n}{5}\
&+2458368binom{n}{6}+10551552binom{n}{7}+28055808binom{n}{8}+47786112binom{n}{9}\
&+52272000binom{n}{10}+35544960binom{n}{11}+13685760binom{n}{12}+2280960binom{n}{13}left.vphantom{binom{n}{2}}right]\
end{align}
$$
answered Aug 7 '15 at 11:05
robjohn♦robjohn
270k27312640
$endgroup$
3
$begingroup$
Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it.
$endgroup$
– Lubin
Aug 7 '15 at 12:06
$begingroup$
Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $binom{n}{0}$. Evaluating $n^{13}-n-c_0binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $binom{n}{1}$. Evaluating $n^{13}-n-c_0binom{n}{0}-c_1binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $binom{n}{2}$. etc. Other than the large numbers, it is pretty simple.
$endgroup$
– robjohn♦
Aug 7 '15 at 12:34
add a comment |
$begingroup$
One Approach
If $kmid n$, then $x^{k+1}-xmid x^{n+1}-x$. Therefore,
$$
begin{array}{}
13&mid&n^{13}-n\
7&mid&n^7-n&mid&n^{13}-n&text{since }6mid12\
5&mid&n^5-n&mid&n^{13}-n&text{since }4mid12\
3&mid&n^3-n&mid&n^{13}-n&text{since }2mid12\
2&mid&n^2-n&mid&n^{13}-n&text{since }1mid12\
end{array}
$$
Since the factors are all relatively prime, we have that
$$
2730=2cdot3cdot5cdot7cdot 13mid n^{13}-n
$$
Another Approach
Decomposing into a sum of combinatorial polynomials
$$
begin{align}
n^{13}-n
&=2730left[vphantom{binom{n}{2}}right.3binom{n}{2}+575binom{n}{3}+22264binom{n}{4}+330044binom{n}{5}\
&+2458368binom{n}{6}+10551552binom{n}{7}+28055808binom{n}{8}+47786112binom{n}{9}\
&+52272000binom{n}{10}+35544960binom{n}{11}+13685760binom{n}{12}+2280960binom{n}{13}left.vphantom{binom{n}{2}}right]\
end{align}
$$
answered Aug 7 '15 at 11:05
robjohn♦robjohn
270k27312640
$endgroup$
One Approach
If $kmid n$, then $x^{k+1}-xmid x^{n+1}-x$. Therefore,
$$
begin{array}{}
13&mid&n^{13}-n\
7&mid&n^7-n&mid&n^{13}-n&text{since }6mid12\
5&mid&n^5-n&mid&n^{13}-n&text{since }4mid12\
3&mid&n^3-n&mid&n^{13}-n&text{since }2mid12\
2&mid&n^2-n&mid&n^{13}-n&text{since }1mid12\
end{array}
$$
Since the factors are all relatively prime, we have that
$$
2730=2cdot3cdot5cdot7cdot 13mid n^{13}-n
$$
Another Approach
Decomposing into a sum of combinatorial polynomials
$$
begin{align}
n^{13}-n
&=2730left[vphantom{binom{n}{2}}right.3binom{n}{2}+575binom{n}{3}+22264binom{n}{4}+330044binom{n}{5}\
&+2458368binom{n}{6}+10551552binom{n}{7}+28055808binom{n}{8}+47786112binom{n}{9}\
&+52272000binom{n}{10}+35544960binom{n}{11}+13685760binom{n}{12}+2280960binom{n}{13}left.vphantom{binom{n}{2}}right]\
end{align}
$$
answered Aug 7 '15 at 11:05
robjohn♦robjohn
270k27312640
edited Aug 7 '15 at 11:31
answered Aug 7 '15 at 11:05
robjohn♦robjohn
270k27312640
answered Aug 7 '15 at 11:05
robjohn♦robjohn
270k27312640
answered Aug 7 '15 at 11:05
robjohn♦robjohn
270k27312640
270k27312640
3
$begingroup$
Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it.
$endgroup$
– Lubin
Aug 7 '15 at 12:06
$begingroup$
Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $binom{n}{0}$. Evaluating $n^{13}-n-c_0binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $binom{n}{1}$. Evaluating $n^{13}-n-c_0binom{n}{0}-c_1binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $binom{n}{2}$. etc. Other than the large numbers, it is pretty simple.
$endgroup$
– robjohn♦
Aug 7 '15 at 12:34
add a comment |
3
$begingroup$
Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it.
$endgroup$
– Lubin
Aug 7 '15 at 12:06
$begingroup$
Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $binom{n}{0}$. Evaluating $n^{13}-n-c_0binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $binom{n}{1}$. Evaluating $n^{13}-n-c_0binom{n}{0}-c_1binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $binom{n}{2}$. etc. Other than the large numbers, it is pretty simple.
$endgroup$
– robjohn♦
Aug 7 '15 at 12:34
3
3
$begingroup$
Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it.
$endgroup$
– Lubin
Aug 7 '15 at 12:06
$begingroup$
Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it.
$endgroup$
– Lubin
Aug 7 '15 at 12:06
$begingroup$
Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $binom{n}{0}$. Evaluating $n^{13}-n-c_0binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $binom{n}{1}$. Evaluating $n^{13}-n-c_0binom{n}{0}-c_1binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $binom{n}{2}$. etc. Other than the large numbers, it is pretty simple.
$endgroup$
– robjohn♦
Aug 7 '15 at 12:34
$begingroup$
Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $binom{n}{0}$. Evaluating $n^{13}-n-c_0binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $binom{n}{1}$. Evaluating $n^{13}-n-c_0binom{n}{0}-c_1binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $binom{n}{2}$. etc. Other than the large numbers, it is pretty simple.
$endgroup$
– robjohn♦
Aug 7 '15 at 12:34
add a comment |
$begingroup$
Notice that $n^{13}-n =n(n^{12}-1)=n(n^6+1)(n^6-1)=n(n^6+1)(n^3+1)(n^3-1)=...$
answered Dec 6 '13 at 21:14
user99680user99680
5,972821
$endgroup$
add a comment |
$begingroup$
Notice that $n^{13}-n =n(n^{12}-1)=n(n^6+1)(n^6-1)=n(n^6+1)(n^3+1)(n^3-1)=...$
answered Dec 6 '13 at 21:14
user99680user99680
5,972821
$endgroup$
add a comment |
$begingroup$
Notice that $n^{13}-n =n(n^{12}-1)=n(n^6+1)(n^6-1)=n(n^6+1)(n^3+1)(n^3-1)=...$
answered Dec 6 '13 at 21:14
user99680user99680
5,972821
$endgroup$
Notice that $n^{13}-n =n(n^{12}-1)=n(n^6+1)(n^6-1)=n(n^6+1)(n^3+1)(n^3-1)=...$
answered Dec 6 '13 at 21:14
user99680user99680
5,972821
answered Dec 6 '13 at 21:14
user99680user99680
5,972821
answered Dec 6 '13 at 21:14
user99680user99680
5,972821
answered Dec 6 '13 at 21:14
user99680user99680
5,972821
5,972821
add a comment |
add a comment |
$begingroup$
Note that $$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5 equiv n^{13} equiv n^6 cdot n^7 equiv n pmod 7.$$
answered Dec 6 '13 at 21:16
Ahaan S. RungtaAhaan S. Rungta
6,53352161
$endgroup$
add a comment |
$begingroup$
Note that $$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5 equiv n^{13} equiv n^6 cdot n^7 equiv n pmod 7.$$
answered Dec 6 '13 at 21:16
Ahaan S. RungtaAhaan S. Rungta
6,53352161
$endgroup$
add a comment |
$begingroup$
Note that $$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5 equiv n^{13} equiv n^6 cdot n^7 equiv n pmod 7.$$
answered Dec 6 '13 at 21:16
Ahaan S. RungtaAhaan S. Rungta
6,53352161
$endgroup$
Note that $$n^{13} equiv n^5 cdot n^5 cdot n^3 equiv n cdot n cdot n^3 equiv n^5 equiv n pmod 5 equiv n^{13} equiv n^6 cdot n^7 equiv n pmod 7.$$
answered Dec 6 '13 at 21:16
Ahaan S. RungtaAhaan S. Rungta
6,53352161
answered Dec 6 '13 at 21:16
Ahaan S. RungtaAhaan S. Rungta
6,53352161
answered Dec 6 '13 at 21:16
Ahaan S. RungtaAhaan S. Rungta
6,53352161
answered Dec 6 '13 at 21:16
Ahaan S. RungtaAhaan S. Rungta
6,53352161
6,53352161
add a comment |
add a comment |
$begingroup$
$, n = 2730 = 2cdot 3cdot 5cdot 7cdot 13 = ,$ product of all primes $rm ,p,$ such that $rm color{#c00}{p!-!1mid 13!-!1}.,$ Now apply
Theorem $ $ For natural numbers $rm:a,e,n:$ with $rm:e,n>1$
$qquadrm n:|:a^{large e}-a:$ for all $rm:a:iff n:$ is squarefree, and prime $rm:p:|:n,Rightarrow, color{#c00}{p!-!1mid e!-!1}$
Proof $ $ See this answer for a short simple proof.
answered Jul 5 '16 at 19:16
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
add a comment |
$begingroup$
$, n = 2730 = 2cdot 3cdot 5cdot 7cdot 13 = ,$ product of all primes $rm ,p,$ such that $rm color{#c00}{p!-!1mid 13!-!1}.,$ Now apply
Theorem $ $ For natural numbers $rm:a,e,n:$ with $rm:e,n>1$
$qquadrm n:|:a^{large e}-a:$ for all $rm:a:iff n:$ is squarefree, and prime $rm:p:|:n,Rightarrow, color{#c00}{p!-!1mid e!-!1}$
Proof $ $ See this answer for a short simple proof.
answered Jul 5 '16 at 19:16
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
add a comment |
$begingroup$
$, n = 2730 = 2cdot 3cdot 5cdot 7cdot 13 = ,$ product of all primes $rm ,p,$ such that $rm color{#c00}{p!-!1mid 13!-!1}.,$ Now apply
Theorem $ $ For natural numbers $rm:a,e,n:$ with $rm:e,n>1$
$qquadrm n:|:a^{large e}-a:$ for all $rm:a:iff n:$ is squarefree, and prime $rm:p:|:n,Rightarrow, color{#c00}{p!-!1mid e!-!1}$
Proof $ $ See this answer for a short simple proof.
answered Jul 5 '16 at 19:16
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
$, n = 2730 = 2cdot 3cdot 5cdot 7cdot 13 = ,$ product of all primes $rm ,p,$ such that $rm color{#c00}{p!-!1mid 13!-!1}.,$ Now apply
Theorem $ $ For natural numbers $rm:a,e,n:$ with $rm:e,n>1$
$qquadrm n:|:a^{large e}-a:$ for all $rm:a:iff n:$ is squarefree, and prime $rm:p:|:n,Rightarrow, color{#c00}{p!-!1mid e!-!1}$
Proof $ $ See this answer for a short simple proof.
answered Jul 5 '16 at 19:16
Bill DubuqueBill Dubuque
213k29196654
edited Jan 28 at 23:01
answered Jul 5 '16 at 19:16
Bill DubuqueBill Dubuque
213k29196654
answered Jul 5 '16 at 19:16
Bill DubuqueBill Dubuque
213k29196654
answered Jul 5 '16 at 19:16
Bill DubuqueBill Dubuque
213k29196654
213k29196654
add a comment |
add a comment |
$begingroup$
$2730 = 2cdot 3cdot 5cdot 7cdot 13$
The Carmichael function or least universal exponent function is composed by least common multiple over prime components, so $lambda(2730) = text{lcm}(lambda(2), lambda(3), lambda(5), lambda(7), lambda(13)) = text{lcm}(1,2,4,6,12)=12$. Note also that $2730$ is square-free, so the exponent cycle will be entered by the first power ($n^1$) for all numbers. Of course numbers coprime to $2730$ enter the cycle at the zeroth power ($1$).
Thus(!) $n^{(1+12)}equiv n^1 bmod 2730$ as required.
answered Dec 21 '17 at 19:55
JoffanJoffan
32.6k43269
$endgroup$
add a comment |
$begingroup$
$2730 = 2cdot 3cdot 5cdot 7cdot 13$
The Carmichael function or least universal exponent function is composed by least common multiple over prime components, so $lambda(2730) = text{lcm}(lambda(2), lambda(3), lambda(5), lambda(7), lambda(13)) = text{lcm}(1,2,4,6,12)=12$. Note also that $2730$ is square-free, so the exponent cycle will be entered by the first power ($n^1$) for all numbers. Of course numbers coprime to $2730$ enter the cycle at the zeroth power ($1$).
Thus(!) $n^{(1+12)}equiv n^1 bmod 2730$ as required.
answered Dec 21 '17 at 19:55
JoffanJoffan
32.6k43269
$endgroup$
add a comment |
$begingroup$
$2730 = 2cdot 3cdot 5cdot 7cdot 13$
The Carmichael function or least universal exponent function is composed by least common multiple over prime components, so $lambda(2730) = text{lcm}(lambda(2), lambda(3), lambda(5), lambda(7), lambda(13)) = text{lcm}(1,2,4,6,12)=12$. Note also that $2730$ is square-free, so the exponent cycle will be entered by the first power ($n^1$) for all numbers. Of course numbers coprime to $2730$ enter the cycle at the zeroth power ($1$).
Thus(!) $n^{(1+12)}equiv n^1 bmod 2730$ as required.
answered Dec 21 '17 at 19:55
JoffanJoffan
32.6k43269
$endgroup$
$2730 = 2cdot 3cdot 5cdot 7cdot 13$
The Carmichael function or least universal exponent function is composed by least common multiple over prime components, so $lambda(2730) = text{lcm}(lambda(2), lambda(3), lambda(5), lambda(7), lambda(13)) = text{lcm}(1,2,4,6,12)=12$. Note also that $2730$ is square-free, so the exponent cycle will be entered by the first power ($n^1$) for all numbers. Of course numbers coprime to $2730$ enter the cycle at the zeroth power ($1$).
Thus(!) $n^{(1+12)}equiv n^1 bmod 2730$ as required.
answered Dec 21 '17 at 19:55
JoffanJoffan
32.6k43269
answered Dec 21 '17 at 19:55
JoffanJoffan
32.6k43269
answered Dec 21 '17 at 19:55
JoffanJoffan
32.6k43269
answered Dec 21 '17 at 19:55
JoffanJoffan
32.6k43269
32.6k43269
add a comment |
add a comment |
$begingroup$
Cute corollary to FLT.
If $p,q $ are primes and $p-1=m|q-1=k$ then
$p|n^p -n=n (n^m-1)|n (n^m-1)(n^{k-m} + n^{k - 2m}+...+n^m+1)=n (n^k-1)=n^q-n $.
So as $1,2,3,4,6,12$ all divide $12$, it follows $2,3,5,7,13$ all divide $n^{13}- n $.
For me personally it was hardest to see that 5 did but $n^{13}-n = (n^8 + n^4 + 1)(n^5- n) $ so ... it does.
answered Jul 5 '16 at 19:53
fleabloodfleablood
73.6k22891
$endgroup$
add a comment |
$begingroup$
Cute corollary to FLT.
If $p,q $ are primes and $p-1=m|q-1=k$ then
$p|n^p -n=n (n^m-1)|n (n^m-1)(n^{k-m} + n^{k - 2m}+...+n^m+1)=n (n^k-1)=n^q-n $.
So as $1,2,3,4,6,12$ all divide $12$, it follows $2,3,5,7,13$ all divide $n^{13}- n $.
For me personally it was hardest to see that 5 did but $n^{13}-n = (n^8 + n^4 + 1)(n^5- n) $ so ... it does.
answered Jul 5 '16 at 19:53
fleabloodfleablood
73.6k22891
$endgroup$
add a comment |
$begingroup$
Cute corollary to FLT.
If $p,q $ are primes and $p-1=m|q-1=k$ then
$p|n^p -n=n (n^m-1)|n (n^m-1)(n^{k-m} + n^{k - 2m}+...+n^m+1)=n (n^k-1)=n^q-n $.
So as $1,2,3,4,6,12$ all divide $12$, it follows $2,3,5,7,13$ all divide $n^{13}- n $.
For me personally it was hardest to see that 5 did but $n^{13}-n = (n^8 + n^4 + 1)(n^5- n) $ so ... it does.
answered Jul 5 '16 at 19:53
fleabloodfleablood
73.6k22891
$endgroup$
Cute corollary to FLT.
If $p,q $ are primes and $p-1=m|q-1=k$ then
$p|n^p -n=n (n^m-1)|n (n^m-1)(n^{k-m} + n^{k - 2m}+...+n^m+1)=n (n^k-1)=n^q-n $.
So as $1,2,3,4,6,12$ all divide $12$, it follows $2,3,5,7,13$ all divide $n^{13}- n $.
For me personally it was hardest to see that 5 did but $n^{13}-n = (n^8 + n^4 + 1)(n^5- n) $ so ... it does.
answered Jul 5 '16 at 19:53
fleabloodfleablood
73.6k22891
edited Jul 5 '16 at 21:37
answered Jul 5 '16 at 19:53
fleabloodfleablood
73.6k22891
answered Jul 5 '16 at 19:53
fleabloodfleablood
73.6k22891
answered Jul 5 '16 at 19:53
fleabloodfleablood
73.6k22891
73.6k22891
add a comment |
add a comment |
$begingroup$
You can find the Chinese remainder theorem very useful.
answered Dec 6 '13 at 21:15
randuserranduser
42838
$endgroup$
add a comment |
$begingroup$
You can find the Chinese remainder theorem very useful.
answered Dec 6 '13 at 21:15
randuserranduser
42838
$endgroup$
add a comment |
$begingroup$
You can find the Chinese remainder theorem very useful.
answered Dec 6 '13 at 21:15
randuserranduser
42838
$endgroup$
You can find the Chinese remainder theorem very useful.
answered Dec 6 '13 at 21:15
randuserranduser
42838
answered Dec 6 '13 at 21:15
randuserranduser
42838
answered Dec 6 '13 at 21:15
randuserranduser
42838
answered Dec 6 '13 at 21:15
randuserranduser
42838
42838
add a comment |
add a comment |
$begingroup$
Here is some way of automating Rob John's method:
You can always use decomposition over polynomials :$quaddisplaystyle Pi_k(n)=k!binom nk=prodlimits_{i=0}^{k-1} (n-i)$
e.g. $ Pi_4(n)=(n-3)(n-2)(n-1)n$
To solve problems of the type: "show $m$ divides the polynomial $P(n)$"
Let have a look at a simpler example using this technique :
Prove $(n^5-n)$ is divisible by 5 by induction.
Though for $n^{13}-n$ it is a bit tedious.
Here is a maple procedure to do it:
> binomexpansion :=proc(P)
local a,b,c,d,i,p,q:
p:=P: d:= degree(P):
printf("%a = ",P):
for i from d to 0 by -1 do
a:=coeff(p,n,i):
q:=expand(binomial(n,i)):
b:=coeff(q,n,i):
c:=a/b:
p:=p-c*q:
if((c>0)and(i<d)) then printf("+"); fi:
if(c<>0) then printf("%d(n,%d)",c,i); fi:
end do: printf("n"):
end proc
> binomexpansion(n^13-n);
n^13-n = 6227020800(n,13)+37362124800(n,12)+97037740800(n,11)+142702560000(n,10)+
130456085760(n,9)+76592355840(n,8)+28805736960(n,7)+6711344640(n,6)+
901020120(n,5)+60780720(n,4)+1569750(n,3)+8190(n,2)
You can notice that all coefficients are divisible by $2730=2.3.5.7.13$.
And since the binomial coefficients are integers, you get the divisibility by $2730$ as a result.
answered Feb 27 at 20:46
zwimzwim
12.6k831
$endgroup$
add a comment |
$begingroup$
Here is some way of automating Rob John's method:
You can always use decomposition over polynomials :$quaddisplaystyle Pi_k(n)=k!binom nk=prodlimits_{i=0}^{k-1} (n-i)$
e.g. $ Pi_4(n)=(n-3)(n-2)(n-1)n$
To solve problems of the type: "show $m$ divides the polynomial $P(n)$"
Let have a look at a simpler example using this technique :
Prove $(n^5-n)$ is divisible by 5 by induction.
Though for $n^{13}-n$ it is a bit tedious.
Here is a maple procedure to do it:
> binomexpansion :=proc(P)
local a,b,c,d,i,p,q:
p:=P: d:= degree(P):
printf("%a = ",P):
for i from d to 0 by -1 do
a:=coeff(p,n,i):
q:=expand(binomial(n,i)):
b:=coeff(q,n,i):
c:=a/b:
p:=p-c*q:
if((c>0)and(i<d)) then printf("+"); fi:
if(c<>0) then printf("%d(n,%d)",c,i); fi:
end do: printf("n"):
end proc
> binomexpansion(n^13-n);
n^13-n = 6227020800(n,13)+37362124800(n,12)+97037740800(n,11)+142702560000(n,10)+
130456085760(n,9)+76592355840(n,8)+28805736960(n,7)+6711344640(n,6)+
901020120(n,5)+60780720(n,4)+1569750(n,3)+8190(n,2)
You can notice that all coefficients are divisible by $2730=2.3.5.7.13$.
And since the binomial coefficients are integers, you get the divisibility by $2730$ as a result.
answered Feb 27 at 20:46
zwimzwim
12.6k831
$endgroup$
add a comment |
$begingroup$
Here is some way of automating Rob John's method:
You can always use decomposition over polynomials :$quaddisplaystyle Pi_k(n)=k!binom nk=prodlimits_{i=0}^{k-1} (n-i)$
e.g. $ Pi_4(n)=(n-3)(n-2)(n-1)n$
To solve problems of the type: "show $m$ divides the polynomial $P(n)$"
Let have a look at a simpler example using this technique :
Prove $(n^5-n)$ is divisible by 5 by induction.
Though for $n^{13}-n$ it is a bit tedious.
Here is a maple procedure to do it:
> binomexpansion :=proc(P)
local a,b,c,d,i,p,q:
p:=P: d:= degree(P):
printf("%a = ",P):
for i from d to 0 by -1 do
a:=coeff(p,n,i):
q:=expand(binomial(n,i)):
b:=coeff(q,n,i):
c:=a/b:
p:=p-c*q:
if((c>0)and(i<d)) then printf("+"); fi:
if(c<>0) then printf("%d(n,%d)",c,i); fi:
end do: printf("n"):
end proc
> binomexpansion(n^13-n);
n^13-n = 6227020800(n,13)+37362124800(n,12)+97037740800(n,11)+142702560000(n,10)+
130456085760(n,9)+76592355840(n,8)+28805736960(n,7)+6711344640(n,6)+
901020120(n,5)+60780720(n,4)+1569750(n,3)+8190(n,2)
You can notice that all coefficients are divisible by $2730=2.3.5.7.13$.
And since the binomial coefficients are integers, you get the divisibility by $2730$ as a result.
answered Feb 27 at 20:46
zwimzwim
12.6k831
$endgroup$
Here is some way of automating Rob John's method:
You can always use decomposition over polynomials :$quaddisplaystyle Pi_k(n)=k!binom nk=prodlimits_{i=0}^{k-1} (n-i)$
e.g. $ Pi_4(n)=(n-3)(n-2)(n-1)n$
To solve problems of the type: "show $m$ divides the polynomial $P(n)$"
Let have a look at a simpler example using this technique :
Prove $(n^5-n)$ is divisible by 5 by induction.
Though for $n^{13}-n$ it is a bit tedious.
Here is a maple procedure to do it:
> binomexpansion :=proc(P)
local a,b,c,d,i,p,q:
p:=P: d:= degree(P):
printf("%a = ",P):
for i from d to 0 by -1 do
a:=coeff(p,n,i):
q:=expand(binomial(n,i)):
b:=coeff(q,n,i):
c:=a/b:
p:=p-c*q:
if((c>0)and(i<d)) then printf("+"); fi:
if(c<>0) then printf("%d(n,%d)",c,i); fi:
end do: printf("n"):
end proc
> binomexpansion(n^13-n);
n^13-n = 6227020800(n,13)+37362124800(n,12)+97037740800(n,11)+142702560000(n,10)+
130456085760(n,9)+76592355840(n,8)+28805736960(n,7)+6711344640(n,6)+
901020120(n,5)+60780720(n,4)+1569750(n,3)+8190(n,2)
You can notice that all coefficients are divisible by $2730=2.3.5.7.13$.
And since the binomial coefficients are integers, you get the divisibility by $2730$ as a result.
answered Feb 27 at 20:46
zwimzwim
12.6k831
answered Feb 27 at 20:46
zwimzwim
12.6k831
answered Feb 27 at 20:46
zwimzwim
12.6k831
answered Feb 27 at 20:46
zwimzwim
12.6k831
12.6k831
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%2f596074%2fhow-to-show-that-2730-mid-n13-n-forall-n-in-mathbbn%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$
It seems like a factorization of $n^{13}-n$ should do it.
$endgroup$
– user99680
Dec 6 '13 at 21:12
$begingroup$
See also math.stackexchange.com/questions/1387239/…
$endgroup$
– Martin Sleziak
Aug 7 '15 at 10:03
$begingroup$
By FLT $5|n^5 - n$ , $7|n^7 - n$ and $3|n^3 - n$. $n^13 - n = n(n^12 - 1) = n(n^6 + 1)(n^6 - 1) = n(n^6+1)(n^3 + 1)(n^3 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n^2 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n+1) (n-1)$. $n^7 - n = n(n^6 - 1)$ is a factor. $n^3 -n = n(n^2 - 1)$ is a factor. 5? well if $n = i mod 5$ if i = 0 5|n if i = 1 5|n - 1. If i = 4 5|n+1. If i = 2 or 3 5|n^6+1.
$endgroup$
– fleablood
Jul 5 '16 at 19:33