0

Can someone check my answers please. I am not confident on the first part but I think my second part is right. I think for the first part there is a better method to use.

Let $a \in \mathbb Z$. We have $a^3 ≡ 1$ mod $11$.

$(i)$ Show that $11$ does not divide $a$ and deduce that $a^{10} ≡ 1$ mod $11$.

Assume for sake of a contradiction that $11 | a$. Then we have $a ≡ 0$ mod $11$. So $a^3 ≡ 0$ mod $11$. By the symmetric property of $\mathbb Z_{11}$ since it is an equivalence relation, $0 ≡ a$ mod $11$. Then by the transitive property of $Z_{11}$, since $0 ≡ a^3$ mod $11$ and $a^3 ≡ 1$ mod $11$, then $0 ≡ 1$ mod $11$, which is clearly false. So we have a contradiction, meaning that $11$ does not divide $a$.

Now, using Fermat's Little Theorem (am I allowed to just state this), since $11$ is prime and $11$ does not divide $a$, we have $a^{10} ≡ 1$ mod $11$. $\square$

$(ii)$ Show that $a^{21} ≡ 1$ mod $11$ and deduce that $a ≡ 1$ mod $11$.

Since $a^3 ≡ 1$ mod $11$, we have $a^{21} ≡ 1$ mod $11$. We also have $a^{10} ≡ 1$ mod $11$, so we can see that $a^{20} ≡ 1$ mod $11$, and so $a^{21} ≡ a$ mod $11$. So again using the fact that $\mathbb Z_{11}$ is an equivalence relation, we have $a ≡ a^{21}$ mod $11$ and $a^{21} ≡ 1$ mod $11$, so by transitive property, $a ≡ 1$ mod $11$ as required. $\square$

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
Nikita Mazepin
  • 1,129
  • 1
  • 12
  • 1
    For the first part, it's a bit quicker to say that if $11\mid a$, then it also divides $a^3$, which is already the contradiction we wanted – Fix Jan 01 '23 at 14:19
  • @Fix Thanks - so basically you took the contrapositive of that statement ? And, does $(ii)$ look ok ? – Nikita Mazepin Jan 01 '23 at 14:28
  • 1
    To me it's more obvious to simply make a table of values and deduce that $a^3 \equiv 1 \iff a \equiv 1 \pmod{11}$. Though this does seem too brute force-y. – Hersh Jan 01 '23 at 14:29
  • @Hersh Actually that does make sense. It would have been easier to do that than thinking of my method and more simpler. Thanks for noting this – Nikita Mazepin Jan 01 '23 at 14:32
  • 2
    @NikitaMazepin your reasoning looks good, just be careful about the wording: $\mathbb{Z}_{11}$ is a ring and the $\equiv$ relation is the "=" in that ring, so multiplication and addition/subtraction works perfectly fine.$$$$ Also for deducing $a\equiv 1$ we could observe that $a^3\equiv a^{10}\equiv 1$, so the order of a divides both 10 and 3, meaning it can only be one – Fix Jan 01 '23 at 14:33
  • @Fix Okay thanks for your help : ) – Nikita Mazepin Jan 01 '23 at 14:35
  • By the linked dupe $\bmod 11\!:\ a^3\equiv 1\!\iff\! \overbrace{(a^3)^{\color{#c00}7}\equiv 1^{\color{#c00}7}}^{\textstyle \ \ \ a\equiv 1}\,$ by taking $\rm\color{#0a0}{cube\ roots}$, by raising to power $\,\color{#0a0}{1/3}\equiv 21/3\equiv 7\bmod{10}\ \ $ – Bill Dubuque Jan 01 '23 at 14:50
  • Your argument is correct. Written more concisely it is $$\bmod 11\!:\ \color{#0a0}{a^3\equiv 1}\Rightarrow \color{#c00}{a\not\equiv 0}\Rightarrow \color{#0a0}1^7\equiv(\color{#0a0}{a^3})^7\equiv a(\color{#c00}{a^{10}})^2\overset{\color{#c00}{\rm F\ell T}}\equiv a(\color{#c00}1)^2\equiv a\qquad$$ Compare to the proof of the $k$'th root method in the dupe. Or: $\,\color{#c00}{1\equiv a^{10}}\equiv a(\color{#0a0}{a^3})^3\equiv a(\color{#0a0}1)^3\equiv a.\ \ $ – Bill Dubuque Jan 01 '23 at 15:08
  • Generally $\,a^j\equiv 1\equiv a^k\Rightarrow a^{\gcd(j,k)}\equiv 1\,$ using $\,\gcd(j,k) = mj+nk\,$ by Bezout, and the above methods amount to different ways of computing the gcd. If 'order' is familar and if $\,j,k\,$ are coprime then the order of $a$ divides coprimes $\,j,k\,$ so the order must be $1,\,$ i.e. $\,a^1\equiv 1\ \ $ – Bill Dubuque Jan 01 '23 at 15:08
  • Once all is clear please delete the question since we already have far too many posts showing these methods. – Bill Dubuque Jan 01 '23 at 15:13
  • 1
    I recommend that you ignore the first comment. Your method using *congruences* is *better* than reverting back to manipulation of divisibility *relations*. One will quickly get lost in complexity if one always works with divisibility relations instead of congruences - which allow is to use or well-honed manipulations of *equations* (vs. far less intuitive (divisibility) *relations*). Ditto for the 3rd comment (the point of such exercises is to develop intuition for congruences (and group theory) - not brute-force (residue) case testing - which quickly becomes infeasible for larger problems). – Bill Dubuque Jan 01 '23 at 15:20
  • Please note that for future questions, for a `solution-verification` question to be on topic you must specify *precisely* which step in the proof you question, and *why so*. This site is not meant to be an open-ended proof checking machine. – Bill Dubuque Jan 01 '23 at 15:23
  • @BillDubuque So my proof by contradiction is okay ? – Nikita Mazepin Jan 01 '23 at 15:54
  • Yes. Normally at this level one doesn't justify every invocation of equivalence relation properties of congruences - just as in manipulation of ordinary equations (doing so obscures the heart of the matter). – Bill Dubuque Jan 01 '23 at 17:09

0 Answers0