Mixing
![how to fix a php registration form 404 error [duplicate]](https://lh3.googleusercontent.com/--f41pLm64rc/AAAAAAAAAAI/AAAAAAAAANg/QfJphk66HiI/s72-c/photo.jpg?sz=32)
$A^{C_p} - I_2$ has all entries divisible by $p$, for an infinite number of positive integers $p$
$begingroup$
Let $A$ be an integer valued matrix, with $det{A} neq 0$. Show that there exists an infinite number of positive integers $p$ for which there exists a constant $C_p$ such that all entries of the matrix $A^{C_p} - I_2$ are divisible by $p$, where $I_2$ is the second order identity matrix.
This is what I have been able to prove:
1) If the matrix is diagonal, with diagonal elements, say $a$ and $b$, then by choosing $p$ coprime to $a$ and $b$ and choosing $C_p = phi(p)$, all elements of $A^{C_p} - I_2$ are divisible by $p$, due to Euler's theorem.
2) If the matrix is, say, $$ A = begin{bmatrix} a & b\ 0&c end{bmatrix},$$
then if $a neq c$ (the $a = c$ case is simple to prove) we can show that
$$A^n = begin{bmatrix} a^n & bleft(frac{a^n - c^n}{a-c}right) \ 0 & c^nend{bmatrix}.$$
Choosing $p$ coprime to $a,c, a-c$, and $C_p = phi(p)$, then the problem is again solved by Euler's theorem.
I cannot prove it if all entries are nonzero. I have been able to show that the gcd of the entries of $A - I_2$ is $leq $ the gcd of the entries of $A^2 - I_2$. If I could prove that the sequence:
$$a_n = text{gcd of entries of } A^{2^n} - I_2$$
does not eventually become stationary, then the problem is solved. Experimenting with Mathematica shows that this is the case.
Any ideas?
linear-algebra elementary-number-theory
asked Jan 15 at 21:05
Tanny SiebenTanny Sieben
34318
$endgroup$
add a comment |
$begingroup$
Let $A$ be an integer valued matrix, with $det{A} neq 0$. Show that there exists an infinite number of positive integers $p$ for which there exists a constant $C_p$ such that all entries of the matrix $A^{C_p} - I_2$ are divisible by $p$, where $I_2$ is the second order identity matrix.
This is what I have been able to prove:
1) If the matrix is diagonal, with diagonal elements, say $a$ and $b$, then by choosing $p$ coprime to $a$ and $b$ and choosing $C_p = phi(p)$, all elements of $A^{C_p} - I_2$ are divisible by $p$, due to Euler's theorem.
2) If the matrix is, say, $$ A = begin{bmatrix} a & b\ 0&c end{bmatrix},$$
then if $a neq c$ (the $a = c$ case is simple to prove) we can show that
$$A^n = begin{bmatrix} a^n & bleft(frac{a^n - c^n}{a-c}right) \ 0 & c^nend{bmatrix}.$$
Choosing $p$ coprime to $a,c, a-c$, and $C_p = phi(p)$, then the problem is again solved by Euler's theorem.
I cannot prove it if all entries are nonzero. I have been able to show that the gcd of the entries of $A - I_2$ is $leq $ the gcd of the entries of $A^2 - I_2$. If I could prove that the sequence:
$$a_n = text{gcd of entries of } A^{2^n} - I_2$$
does not eventually become stationary, then the problem is solved. Experimenting with Mathematica shows that this is the case.
Any ideas?
linear-algebra elementary-number-theory
asked Jan 15 at 21:05
Tanny SiebenTanny Sieben
34318
$endgroup$
$begingroup$
Let $p$ be any prime such that $p nmid det A$. Then, the projection of the matrix $A$ onto the corresponding matrix ring over the finite field $mathbb{F}_p$ is invertible (since its determinant is nonzero in $mathbb{F}_p$), and thus it belongs to the finite group $operatorname{GL}_nleft(mathbb{F}_pright)$. But an element of a finite group always has finite order. Denoting this order by $C_p$, you thus have $A^{C_p} equiv I_n mod p$ (in the sense that all entries of $A^{C_p}$ are congruent to the respective entries of $I_n$ modulo $p$).
$endgroup$
– darij grinberg
Jan 26 at 1:52
add a comment |
$begingroup$
Let $A$ be an integer valued matrix, with $det{A} neq 0$. Show that there exists an infinite number of positive integers $p$ for which there exists a constant $C_p$ such that all entries of the matrix $A^{C_p} - I_2$ are divisible by $p$, where $I_2$ is the second order identity matrix.
This is what I have been able to prove:
1) If the matrix is diagonal, with diagonal elements, say $a$ and $b$, then by choosing $p$ coprime to $a$ and $b$ and choosing $C_p = phi(p)$, all elements of $A^{C_p} - I_2$ are divisible by $p$, due to Euler's theorem.
2) If the matrix is, say, $$ A = begin{bmatrix} a & b\ 0&c end{bmatrix},$$
then if $a neq c$ (the $a = c$ case is simple to prove) we can show that
$$A^n = begin{bmatrix} a^n & bleft(frac{a^n - c^n}{a-c}right) \ 0 & c^nend{bmatrix}.$$
Choosing $p$ coprime to $a,c, a-c$, and $C_p = phi(p)$, then the problem is again solved by Euler's theorem.
I cannot prove it if all entries are nonzero. I have been able to show that the gcd of the entries of $A - I_2$ is $leq $ the gcd of the entries of $A^2 - I_2$. If I could prove that the sequence:
$$a_n = text{gcd of entries of } A^{2^n} - I_2$$
does not eventually become stationary, then the problem is solved. Experimenting with Mathematica shows that this is the case.
Any ideas?
linear-algebra elementary-number-theory
asked Jan 15 at 21:05
Tanny SiebenTanny Sieben
34318
$endgroup$
Let $A$ be an integer valued matrix, with $det{A} neq 0$. Show that there exists an infinite number of positive integers $p$ for which there exists a constant $C_p$ such that all entries of the matrix $A^{C_p} - I_2$ are divisible by $p$, where $I_2$ is the second order identity matrix.
This is what I have been able to prove:
1) If the matrix is diagonal, with diagonal elements, say $a$ and $b$, then by choosing $p$ coprime to $a$ and $b$ and choosing $C_p = phi(p)$, all elements of $A^{C_p} - I_2$ are divisible by $p$, due to Euler's theorem.
2) If the matrix is, say, $$ A = begin{bmatrix} a & b\ 0&c end{bmatrix},$$
then if $a neq c$ (the $a = c$ case is simple to prove) we can show that
$$A^n = begin{bmatrix} a^n & bleft(frac{a^n - c^n}{a-c}right) \ 0 & c^nend{bmatrix}.$$
Choosing $p$ coprime to $a,c, a-c$, and $C_p = phi(p)$, then the problem is again solved by Euler's theorem.
I cannot prove it if all entries are nonzero. I have been able to show that the gcd of the entries of $A - I_2$ is $leq $ the gcd of the entries of $A^2 - I_2$. If I could prove that the sequence:
$$a_n = text{gcd of entries of } A^{2^n} - I_2$$
does not eventually become stationary, then the problem is solved. Experimenting with Mathematica shows that this is the case.
Any ideas?
linear-algebra elementary-number-theory
linear-algebra elementary-number-theory
asked Jan 15 at 21:05
Tanny SiebenTanny Sieben
34318
asked Jan 15 at 21:05
Tanny SiebenTanny Sieben
34318
asked Jan 15 at 21:05
Tanny SiebenTanny Sieben
34318
asked Jan 15 at 21:05
Tanny SiebenTanny Sieben
34318
asked Jan 15 at 21:05
Tanny SiebenTanny Sieben
34318
34318
$begingroup$
Let $p$ be any prime such that $p nmid det A$. Then, the projection of the matrix $A$ onto the corresponding matrix ring over the finite field $mathbb{F}_p$ is invertible (since its determinant is nonzero in $mathbb{F}_p$), and thus it belongs to the finite group $operatorname{GL}_nleft(mathbb{F}_pright)$. But an element of a finite group always has finite order. Denoting this order by $C_p$, you thus have $A^{C_p} equiv I_n mod p$ (in the sense that all entries of $A^{C_p}$ are congruent to the respective entries of $I_n$ modulo $p$).
$endgroup$
– darij grinberg
Jan 26 at 1:52
add a comment |
$begingroup$
Let $p$ be any prime such that $p nmid det A$. Then, the projection of the matrix $A$ onto the corresponding matrix ring over the finite field $mathbb{F}_p$ is invertible (since its determinant is nonzero in $mathbb{F}_p$), and thus it belongs to the finite group $operatorname{GL}_nleft(mathbb{F}_pright)$. But an element of a finite group always has finite order. Denoting this order by $C_p$, you thus have $A^{C_p} equiv I_n mod p$ (in the sense that all entries of $A^{C_p}$ are congruent to the respective entries of $I_n$ modulo $p$).
$endgroup$
– darij grinberg
Jan 26 at 1:52
$begingroup$
Let $p$ be any prime such that $p nmid det A$. Then, the projection of the matrix $A$ onto the corresponding matrix ring over the finite field $mathbb{F}_p$ is invertible (since its determinant is nonzero in $mathbb{F}_p$), and thus it belongs to the finite group $operatorname{GL}_nleft(mathbb{F}_pright)$. But an element of a finite group always has finite order. Denoting this order by $C_p$, you thus have $A^{C_p} equiv I_n mod p$ (in the sense that all entries of $A^{C_p}$ are congruent to the respective entries of $I_n$ modulo $p$).
$endgroup$
– darij grinberg
Jan 26 at 1:52
$begingroup$
Let $p$ be any prime such that $p nmid det A$. Then, the projection of the matrix $A$ onto the corresponding matrix ring over the finite field $mathbb{F}_p$ is invertible (since its determinant is nonzero in $mathbb{F}_p$), and thus it belongs to the finite group $operatorname{GL}_nleft(mathbb{F}_pright)$. But an element of a finite group always has finite order. Denoting this order by $C_p$, you thus have $A^{C_p} equiv I_n mod p$ (in the sense that all entries of $A^{C_p}$ are congruent to the respective entries of $I_n$ modulo $p$).
$endgroup$
– darij grinberg
Jan 26 at 1:52
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I will look for some reference for this: given a nonzero integer $n,$ there are infinitely many primes for which $n$ is a square (a quadratic residue). The two proofs i can think of use quadratic reciprocity, Dirichlet's result on primes in arithmetic progressions, or Chebotarev density.
https://number.subwiki.org/wiki/Every_integer_is_a_quadratic_residue_for_infinitely_many_primes
they use:
https://number.subwiki.org/wiki/Set_of_prime_divisors_of_values_of_nonconstant_polynomial_with_integer_coefficients_is_infinite
Given a matrix
$$
left(
begin{array}{cc}
alpha & beta \
gamma & delta
end{array}
right)
$$
the integer in question is
$$ n = (alpha - delta)^2 + 4 beta gamma $$
If we take an odd prime $p$ that does not divide the determinant $alpha delta - beta gamma$ or $n,$ and for which $n$ is a quadratic residue, then the eigenvalues of the matrix lie in the field with $p$ elements as
$$ frac{alpha + delta pm sqrt n}{2}. $$
Then we can diagonalize the matrix as some $P^{-1}DP = A$ over the field with $p$ elements. There is an exponent such that $D^C = I pmod p.$ The same applies to $A.$
answered Jan 16 at 1:45
Will JagyWill Jagy
103k5102200
$endgroup$
$begingroup$
Couple of questions: 1. Why shouldn't $p$ divide the determinant? 2. By FLT, is it enough to choose $C=p-1$ such that $D^C = I$ (mod $p$)? 3. How can we conclude that "the same applies to A"? Do we just multiply to the left and to the right with $P$ and $P^{-1}$?
$endgroup$
– Tanny Sieben
Jan 16 at 6:58
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%2f3074966%2fac-p-i-2-has-all-entries-divisible-by-p-for-an-infinite-number-of-posi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I will look for some reference for this: given a nonzero integer $n,$ there are infinitely many primes for which $n$ is a square (a quadratic residue). The two proofs i can think of use quadratic reciprocity, Dirichlet's result on primes in arithmetic progressions, or Chebotarev density.
https://number.subwiki.org/wiki/Every_integer_is_a_quadratic_residue_for_infinitely_many_primes
they use:
https://number.subwiki.org/wiki/Set_of_prime_divisors_of_values_of_nonconstant_polynomial_with_integer_coefficients_is_infinite
Given a matrix
$$
left(
begin{array}{cc}
alpha & beta \
gamma & delta
end{array}
right)
$$
the integer in question is
$$ n = (alpha - delta)^2 + 4 beta gamma $$
If we take an odd prime $p$ that does not divide the determinant $alpha delta - beta gamma$ or $n,$ and for which $n$ is a quadratic residue, then the eigenvalues of the matrix lie in the field with $p$ elements as
$$ frac{alpha + delta pm sqrt n}{2}. $$
Then we can diagonalize the matrix as some $P^{-1}DP = A$ over the field with $p$ elements. There is an exponent such that $D^C = I pmod p.$ The same applies to $A.$
answered Jan 16 at 1:45
Will JagyWill Jagy
103k5102200
$endgroup$
$begingroup$
Couple of questions: 1. Why shouldn't $p$ divide the determinant? 2. By FLT, is it enough to choose $C=p-1$ such that $D^C = I$ (mod $p$)? 3. How can we conclude that "the same applies to A"? Do we just multiply to the left and to the right with $P$ and $P^{-1}$?
$endgroup$
– Tanny Sieben
Jan 16 at 6:58
add a comment |
$begingroup$
I will look for some reference for this: given a nonzero integer $n,$ there are infinitely many primes for which $n$ is a square (a quadratic residue). The two proofs i can think of use quadratic reciprocity, Dirichlet's result on primes in arithmetic progressions, or Chebotarev density.
https://number.subwiki.org/wiki/Every_integer_is_a_quadratic_residue_for_infinitely_many_primes
they use:
https://number.subwiki.org/wiki/Set_of_prime_divisors_of_values_of_nonconstant_polynomial_with_integer_coefficients_is_infinite
Given a matrix
$$
left(
begin{array}{cc}
alpha & beta \
gamma & delta
end{array}
right)
$$
the integer in question is
$$ n = (alpha - delta)^2 + 4 beta gamma $$
If we take an odd prime $p$ that does not divide the determinant $alpha delta - beta gamma$ or $n,$ and for which $n$ is a quadratic residue, then the eigenvalues of the matrix lie in the field with $p$ elements as
$$ frac{alpha + delta pm sqrt n}{2}. $$
Then we can diagonalize the matrix as some $P^{-1}DP = A$ over the field with $p$ elements. There is an exponent such that $D^C = I pmod p.$ The same applies to $A.$
answered Jan 16 at 1:45
Will JagyWill Jagy
103k5102200
$endgroup$
$begingroup$
Couple of questions: 1. Why shouldn't $p$ divide the determinant? 2. By FLT, is it enough to choose $C=p-1$ such that $D^C = I$ (mod $p$)? 3. How can we conclude that "the same applies to A"? Do we just multiply to the left and to the right with $P$ and $P^{-1}$?
$endgroup$
– Tanny Sieben
Jan 16 at 6:58
add a comment |
$begingroup$
I will look for some reference for this: given a nonzero integer $n,$ there are infinitely many primes for which $n$ is a square (a quadratic residue). The two proofs i can think of use quadratic reciprocity, Dirichlet's result on primes in arithmetic progressions, or Chebotarev density.
https://number.subwiki.org/wiki/Every_integer_is_a_quadratic_residue_for_infinitely_many_primes
they use:
https://number.subwiki.org/wiki/Set_of_prime_divisors_of_values_of_nonconstant_polynomial_with_integer_coefficients_is_infinite
Given a matrix
$$
left(
begin{array}{cc}
alpha & beta \
gamma & delta
end{array}
right)
$$
the integer in question is
$$ n = (alpha - delta)^2 + 4 beta gamma $$
If we take an odd prime $p$ that does not divide the determinant $alpha delta - beta gamma$ or $n,$ and for which $n$ is a quadratic residue, then the eigenvalues of the matrix lie in the field with $p$ elements as
$$ frac{alpha + delta pm sqrt n}{2}. $$
Then we can diagonalize the matrix as some $P^{-1}DP = A$ over the field with $p$ elements. There is an exponent such that $D^C = I pmod p.$ The same applies to $A.$
answered Jan 16 at 1:45
Will JagyWill Jagy
103k5102200
$endgroup$
I will look for some reference for this: given a nonzero integer $n,$ there are infinitely many primes for which $n$ is a square (a quadratic residue). The two proofs i can think of use quadratic reciprocity, Dirichlet's result on primes in arithmetic progressions, or Chebotarev density.
https://number.subwiki.org/wiki/Every_integer_is_a_quadratic_residue_for_infinitely_many_primes
they use:
https://number.subwiki.org/wiki/Set_of_prime_divisors_of_values_of_nonconstant_polynomial_with_integer_coefficients_is_infinite
Given a matrix
$$
left(
begin{array}{cc}
alpha & beta \
gamma & delta
end{array}
right)
$$
the integer in question is
$$ n = (alpha - delta)^2 + 4 beta gamma $$
If we take an odd prime $p$ that does not divide the determinant $alpha delta - beta gamma$ or $n,$ and for which $n$ is a quadratic residue, then the eigenvalues of the matrix lie in the field with $p$ elements as
$$ frac{alpha + delta pm sqrt n}{2}. $$
Then we can diagonalize the matrix as some $P^{-1}DP = A$ over the field with $p$ elements. There is an exponent such that $D^C = I pmod p.$ The same applies to $A.$
answered Jan 16 at 1:45
Will JagyWill Jagy
103k5102200
edited Jan 16 at 1:51
answered Jan 16 at 1:45
Will JagyWill Jagy
103k5102200
answered Jan 16 at 1:45
Will JagyWill Jagy
103k5102200
answered Jan 16 at 1:45
Will JagyWill Jagy
103k5102200
103k5102200
$begingroup$
Couple of questions: 1. Why shouldn't $p$ divide the determinant? 2. By FLT, is it enough to choose $C=p-1$ such that $D^C = I$ (mod $p$)? 3. How can we conclude that "the same applies to A"? Do we just multiply to the left and to the right with $P$ and $P^{-1}$?
$endgroup$
– Tanny Sieben
Jan 16 at 6:58
add a comment |
$begingroup$
Couple of questions: 1. Why shouldn't $p$ divide the determinant? 2. By FLT, is it enough to choose $C=p-1$ such that $D^C = I$ (mod $p$)? 3. How can we conclude that "the same applies to A"? Do we just multiply to the left and to the right with $P$ and $P^{-1}$?
$endgroup$
– Tanny Sieben
Jan 16 at 6:58
$begingroup$
Couple of questions: 1. Why shouldn't $p$ divide the determinant? 2. By FLT, is it enough to choose $C=p-1$ such that $D^C = I$ (mod $p$)? 3. How can we conclude that "the same applies to A"? Do we just multiply to the left and to the right with $P$ and $P^{-1}$?
$endgroup$
– Tanny Sieben
Jan 16 at 6:58
$begingroup$
Couple of questions: 1. Why shouldn't $p$ divide the determinant? 2. By FLT, is it enough to choose $C=p-1$ such that $D^C = I$ (mod $p$)? 3. How can we conclude that "the same applies to A"? Do we just multiply to the left and to the right with $P$ and $P^{-1}$?
$endgroup$
– Tanny Sieben
Jan 16 at 6:58
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%2f3074966%2fac-p-i-2-has-all-entries-divisible-by-p-for-an-infinite-number-of-posi%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
$begingroup$
Let $p$ be any prime such that $p nmid det A$. Then, the projection of the matrix $A$ onto the corresponding matrix ring over the finite field $mathbb{F}_p$ is invertible (since its determinant is nonzero in $mathbb{F}_p$), and thus it belongs to the finite group $operatorname{GL}_nleft(mathbb{F}_pright)$. But an element of a finite group always has finite order. Denoting this order by $C_p$, you thus have $A^{C_p} equiv I_n mod p$ (in the sense that all entries of $A^{C_p}$ are congruent to the respective entries of $I_n$ modulo $p$).
$endgroup$
– darij grinberg
Jan 26 at 1:52