Fdtxjr

Non-trope happy ending?

Limits and Infinite Integration by Parts

Can I say "fingers" when referring to toes?

Why is so much work done on numerical verification of the Riemann Hypothesis?

PTIJ: Haman's bad computer

Why is the "ls" command showing permissions of files in a FAT32 partition?

It grows, but water kills it

How could a planet have erratic days?

Why Shazam when there is already Superman?

Mimic lecturing on blackboard, facing audience

Did arcade monitors have same pixel aspect ratio as TV sets?

Calculate sum of polynomial roots

What is the highest possible scrabble score for placing a single tile

What is going on with 'gets(stdin)' on the site coderbyte?

Calculating total slots

What should you do if you miss a job interview (deliberately)?

Strong empirical falsification of quantum mechanics based on vacuum energy density

Can a Canadian Travel to the USA twice, less than 180 days each time?

Does the Linux kernel need a file system to run?

Why "had" in "[something] we would have made had we used [something]"?

Is aluminum electrical wire used on aircraft?

Plot of a tornado-shaped surface

Redundant comparison & "if" before assignment

How does the math work for Perception checks?

Noninvertible matrix mod s from an invertible matrix

The productrelation matrix is equivalent to the product of the matrix of the relationsProving modular implicatonMatrix Induction proofs using $rm mod$.Modular arithmetic and using in well-ordering principleAn example of a sentence $sigma$ s.t. $textGL_n(mathbbQ(sqrt3)) models sigma$ and $textGL_n(mathbbQ(sqrt2)) notmodels sigma$Multiple solutions of the Cat MapModulo, help solvingWhy does it follow from $ns = 1 - ar$ that $ar equiv 1 mod n$?$c in mathbbN$, so that $c cdot 11 = 23 mod 103$exist $x$ such that $x^k equiv m$ mod $(p_1cdot p_2) Leftrightarrow $ exists $x_1,x_2$ : $x_1^kequiv m(p_1)$ and $x_2^kequiv m(p_2)$

2

1

$begingroup$

Let $Ain M_2(mathbbZ)$ with nonzero determinant. Show that there exist infinitely many numbers $sinmathbbN$ such that $$
exists a_sinmathbbN^*:A^a_s-I equiv Omod s.
$$

My attempt is to use prove by contradiction. Suppose that for all $x$ in a finite set of natural number and for all $ane 0$ natural number, we have $$
A^a-Inotequiv O mod x Leftrightarrow A^anotequiv I mod x.
$$
Applying determinant to the above formula, we get that$$
adet(A)notequiv 1 mod x.
$$ So, we get that $x$ not devide $adet(A)-1$ or, for some $kinmathbbZ$, we have $$
adet(A)-1ne kx,quad forall xinx_1,...,x_l text and ainmathbbN^*.
$$
Moreover we get that$$
det(A)ne frackx+1a,quad forall xinx_1,...,x_l text and ainmathbbN^*.
$$ Then letting $a$ go to infinity, we obtain $$
det(A)ne 0,
$$ which not contradict the hypothesis.
Does this argument really can work? Does exists other path to get the claim in the conclusion? Thanks in advanced!

matrices group-theory modular-arithmetic

share|cite|improve this question

edited Mar 15 at 2:53

stefano

asked Mar 15 at 2:37

stefanostefano

1708

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't understand your proof. You start with a statement that is not a negation of what you are trying to prove, then how can it be a proof by contradiction? Namely, you start with "For all $x$ in a finite subset of $mathbb N$ …". But the true negation of what you want to prove is "For all but finitely many $s in mathbb N$, $A^a notequiv I mod s$ for all $a in mathbb N^*$".
  $endgroup$
  – M. Vinay
  Mar 15 at 3:25
  
  

  
  
  
  

add a comment | 

2

1

$begingroup$

Let $Ain M_2(mathbbZ)$ with nonzero determinant. Show that there exist infinitely many numbers $sinmathbbN$ such that $$
exists a_sinmathbbN^*:A^a_s-I equiv Omod s.
$$

My attempt is to use prove by contradiction. Suppose that for all $x$ in a finite set of natural number and for all $ane 0$ natural number, we have $$
A^a-Inotequiv O mod x Leftrightarrow A^anotequiv I mod x.
$$
Applying determinant to the above formula, we get that$$
adet(A)notequiv 1 mod x.
$$ So, we get that $x$ not devide $adet(A)-1$ or, for some $kinmathbbZ$, we have $$
adet(A)-1ne kx,quad forall xinx_1,...,x_l text and ainmathbbN^*.
$$
Moreover we get that$$
det(A)ne frackx+1a,quad forall xinx_1,...,x_l text and ainmathbbN^*.
$$ Then letting $a$ go to infinity, we obtain $$
det(A)ne 0,
$$ which not contradict the hypothesis.
Does this argument really can work? Does exists other path to get the claim in the conclusion? Thanks in advanced!

matrices group-theory modular-arithmetic

share|cite|improve this question

edited Mar 15 at 2:53

stefano

asked Mar 15 at 2:37

stefanostefano

1708

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't understand your proof. You start with a statement that is not a negation of what you are trying to prove, then how can it be a proof by contradiction? Namely, you start with "For all $x$ in a finite subset of $mathbb N$ …". But the true negation of what you want to prove is "For all but finitely many $s in mathbb N$, $A^a notequiv I mod s$ for all $a in mathbb N^*$".
  $endgroup$
  – M. Vinay
  Mar 15 at 3:25
  
  

  
  
  
  

add a comment | 

$begingroup$

Let $Ain M_2(mathbbZ)$ with nonzero determinant. Show that there exist infinitely many numbers $sinmathbbN$ such that $$
exists a_sinmathbbN^*:A^a_s-I equiv Omod s.
$$

My attempt is to use prove by contradiction. Suppose that for all $x$ in a finite set of natural number and for all $ane 0$ natural number, we have $$
A^a-Inotequiv O mod x Leftrightarrow A^anotequiv I mod x.
$$
Applying determinant to the above formula, we get that$$
adet(A)notequiv 1 mod x.
$$ So, we get that $x$ not devide $adet(A)-1$ or, for some $kinmathbbZ$, we have $$
adet(A)-1ne kx,quad forall xinx_1,...,x_l text and ainmathbbN^*.
$$
Moreover we get that$$
det(A)ne frackx+1a,quad forall xinx_1,...,x_l text and ainmathbbN^*.
$$ Then letting $a$ go to infinity, we obtain $$
det(A)ne 0,
$$ which not contradict the hypothesis.
Does this argument really can work? Does exists other path to get the claim in the conclusion? Thanks in advanced!

matrices group-theory modular-arithmetic

share|cite|improve this question

edited Mar 15 at 2:53

stefano

asked Mar 15 at 2:37

stefanostefano

1708

$endgroup$

share|cite|improve this question

edited Mar 15 at 2:53

stefano

asked Mar 15 at 2:37

stefanostefano

1708

share|cite|improve this question

edited Mar 15 at 2:53

stefano

asked Mar 15 at 2:37

stefanostefano

1708

asked Mar 15 at 2:37

stefanostefano

1708

asked Mar 15 at 2:37

stefanostefano

1708

1 Answer
1

active

oldest

votes

1

$begingroup$

Hints:

Let $det A = d ne 0$ (over $mathbb Z$).

1. Are there infinitely many positive integers $s$ such that $d notequiv 0 mod s$? Yes (justify, by specifying which values of $s$ guarantee this).


2. For which of these $s$ will $A in M_2(mathbb Z_s)$ be invertible? Are there infinitely many such $s$?


3. For such an $s$ as in Point 2, consider $A in M_2(mathbb Z_s)$. Since it is invertible, it belongs to the group of units of $M_2(mathbb Z_s)$ [i.e., $GL_2(mathbb Z_s)$]. What can be said about the order of this group? What does that imply about the order of $A$ (as a group element)?

share|cite|improve this answer

edited Mar 16 at 2:18

answered Mar 15 at 3:20

M. VinayM. Vinay

7,05322135

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'll delete the comment then!
  $endgroup$
  – Derek Holt
  Mar 15 at 5:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For the determinant to be a unit, nonzero modulo $s$ is not enough. It should be ”relatively prime to $s$”
  $endgroup$
  – i707107
  Mar 15 at 5:59
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @i707107 Of course, in mind I'd initially decided to argue only for prime $s$, but forgot that later on. Thanks!
  $endgroup$
  – M. Vinay
  Mar 15 at 6:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @i707107 Edited the answer to reflect this (but still keeping it as a hint without giving it away).
  $endgroup$
  – M. Vinay
  Mar 15 at 6:38
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  In the last point, do you mean $GL_2(mathbbZ_s)$? The group $GL_2(mathbbZ)$ is an infinite group.
  $endgroup$
  – i707107
  Mar 15 at 21:05
  

  
  
  
  

 | 
show 1 more 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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3148826%2fnoninvertible-matrix-mod-s-from-an-invertible-matrix%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Hints:

Let $det A = d ne 0$ (over $mathbb Z$).

1. Are there infinitely many positive integers $s$ such that $d notequiv 0 mod s$? Yes (justify, by specifying which values of $s$ guarantee this).


2. For which of these $s$ will $A in M_2(mathbb Z_s)$ be invertible? Are there infinitely many such $s$?


3. For such an $s$ as in Point 2, consider $A in M_2(mathbb Z_s)$. Since it is invertible, it belongs to the group of units of $M_2(mathbb Z_s)$ [i.e., $GL_2(mathbb Z_s)$]. What can be said about the order of this group? What does that imply about the order of $A$ (as a group element)?

share|cite|improve this answer

edited Mar 16 at 2:18

answered Mar 15 at 3:20

M. VinayM. Vinay

7,05322135

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'll delete the comment then!
  $endgroup$
  – Derek Holt
  Mar 15 at 5:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For the determinant to be a unit, nonzero modulo $s$ is not enough. It should be ”relatively prime to $s$”
  $endgroup$
  – i707107
  Mar 15 at 5:59
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @i707107 Of course, in mind I'd initially decided to argue only for prime $s$, but forgot that later on. Thanks!
  $endgroup$
  – M. Vinay
  Mar 15 at 6:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @i707107 Edited the answer to reflect this (but still keeping it as a hint without giving it away).
  $endgroup$
  – M. Vinay
  Mar 15 at 6:38
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  In the last point, do you mean $GL_2(mathbbZ_s)$? The group $GL_2(mathbbZ)$ is an infinite group.
  $endgroup$
  – i707107
  Mar 15 at 21:05
  

  
  
  
  

 | 
show 1 more comment

1

$begingroup$

Hints:

Let $det A = d ne 0$ (over $mathbb Z$).

1. Are there infinitely many positive integers $s$ such that $d notequiv 0 mod s$? Yes (justify, by specifying which values of $s$ guarantee this).


2. For which of these $s$ will $A in M_2(mathbb Z_s)$ be invertible? Are there infinitely many such $s$?


3. For such an $s$ as in Point 2, consider $A in M_2(mathbb Z_s)$. Since it is invertible, it belongs to the group of units of $M_2(mathbb Z_s)$ [i.e., $GL_2(mathbb Z_s)$]. What can be said about the order of this group? What does that imply about the order of $A$ (as a group element)?

share|cite|improve this answer

edited Mar 16 at 2:18

answered Mar 15 at 3:20

M. VinayM. Vinay

7,05322135

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'll delete the comment then!
  $endgroup$
  – Derek Holt
  Mar 15 at 5:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For the determinant to be a unit, nonzero modulo $s$ is not enough. It should be ”relatively prime to $s$”
  $endgroup$
  – i707107
  Mar 15 at 5:59
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @i707107 Of course, in mind I'd initially decided to argue only for prime $s$, but forgot that later on. Thanks!
  $endgroup$
  – M. Vinay
  Mar 15 at 6:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @i707107 Edited the answer to reflect this (but still keeping it as a hint without giving it away).
  $endgroup$
  – M. Vinay
  Mar 15 at 6:38
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  In the last point, do you mean $GL_2(mathbbZ_s)$? The group $GL_2(mathbbZ)$ is an infinite group.
  $endgroup$
  – i707107
  Mar 15 at 21:05
  

  
  
  
  

 | 
show 1 more comment

$begingroup$

Hints:

Let $det A = d ne 0$ (over $mathbb Z$).

1. Are there infinitely many positive integers $s$ such that $d notequiv 0 mod s$? Yes (justify, by specifying which values of $s$ guarantee this).


2. For which of these $s$ will $A in M_2(mathbb Z_s)$ be invertible? Are there infinitely many such $s$?


3. For such an $s$ as in Point 2, consider $A in M_2(mathbb Z_s)$. Since it is invertible, it belongs to the group of units of $M_2(mathbb Z_s)$ [i.e., $GL_2(mathbb Z_s)$]. What can be said about the order of this group? What does that imply about the order of $A$ (as a group element)?

share|cite|improve this answer

edited Mar 16 at 2:18

answered Mar 15 at 3:20

M. VinayM. Vinay

7,05322135

$endgroup$

share|cite|improve this answer

edited Mar 16 at 2:18

answered Mar 15 at 3:20

M. VinayM. Vinay

7,05322135

answered Mar 15 at 3:20

M. VinayM. Vinay

7,05322135

answered Mar 15 at 3:20

M. VinayM. Vinay

7,05322135