Skip to main content
Mathematics

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

$11^2=121\equiv 4\pmod{13}$

$11^3\equiv4\cdot 11\equiv 5$

$11^4=(11^2)^2\equiv 4^2=16\equiv 3$

$11^5\equiv3\cdot11=33\equiv 7$

$11^6\equiv7\cdot 11= 77=-1$

$\implies 11\cdot 11^5\equiv-1\implies (11)^{-1}\equiv -11^5\equiv -7\equiv 6\pmod{13}$

Alternatively, using [convergent][1]convergent property of continued fraction,

$\frac{13}{11}=1+\frac 2{11}=1+\frac1{\frac{11}2}=1+\frac1{5+\frac12}$

So, the last but one convergent is $1+\frac15=\frac 6 5$

So, $11\cdot 6-13\cdot 5=66-65=1\implies 11\cdot 6\equiv 1\pmod{13}$ $\implies (11)^{-1}\equiv 6\pmod{13}$ [1]: http://en.wikipedia.org/wiki/Convergent_%28continued_fraction%29

$11^2=121\equiv 4\pmod{13}$

$11^3\equiv4\cdot 11\equiv 5$

$11^4=(11^2)^2\equiv 4^2=16\equiv 3$

$11^5\equiv3\cdot11=33\equiv 7$

$11^6\equiv7\cdot 11= 77=-1$

$\implies 11\cdot 11^5\equiv-1\implies (11)^{-1}\equiv -11^5\equiv -7\equiv 6\pmod{13}$

Alternatively, using [convergent][1] property of continued fraction,

$\frac{13}{11}=1+\frac 2{11}=1+\frac1{\frac{11}2}=1+\frac1{5+\frac12}$

So, the last but one convergent is $1+\frac15=\frac 6 5$

So, $11\cdot 6-13\cdot 5=66-65=1\implies 11\cdot 6\equiv 1\pmod{13}$ $\implies (11)^{-1}\equiv 6\pmod{13}$ [1]: http://en.wikipedia.org/wiki/Convergent_%28continued_fraction%29

$11^2=121\equiv 4\pmod{13}$

$11^3\equiv4\cdot 11\equiv 5$

$11^4=(11^2)^2\equiv 4^2=16\equiv 3$

$11^5\equiv3\cdot11=33\equiv 7$

$11^6\equiv7\cdot 11= 77=-1$

$\implies 11\cdot 11^5\equiv-1\implies (11)^{-1}\equiv -11^5\equiv -7\equiv 6\pmod{13}$

Alternatively, using convergent property of continued fraction,

$\frac{13}{11}=1+\frac 2{11}=1+\frac1{\frac{11}2}=1+\frac1{5+\frac12}$

So, the last but one convergent is $1+\frac15=\frac 6 5$

So, $11\cdot 6-13\cdot 5=66-65=1\implies 11\cdot 6\equiv 1\pmod{13}$ $\implies (11)^{-1}\equiv 6\pmod{13}$

added 395 characters in body
Source Link
lab bhattacharjee
lab bhattacharjee
  • 280k
  • 20
  • 213
  • 338

$11^2=121\equiv 4\pmod{13}$

$11^3\equiv4\cdot 11\equiv 5$

$11^4=(11^2)^2\equiv 4^2=16\equiv 3$

$11^5\equiv3\cdot11=33\equiv 7$

$11^6\equiv7\cdot 11= 77=-1$

$\implies 11\cdot 11^5\equiv-1\implies (11)^{-1}\equiv -11^5\equiv -7\equiv 6\pmod{13}$

Alternatively, using [convergent][1] property of continued fraction,

$\frac{13}{11}=1+\frac 2{11}=1+\frac1{\frac{11}2}=1+\frac1{5+\frac12}$

So, the last but one convergent is $1+\frac15=\frac 6 5$

So, $11\cdot 6-13\cdot 5=66-65=1\implies 11\cdot 6\equiv 1\pmod{13}$ $\implies (11)^{-1}\equiv 6\pmod{13}$ [1]: http://en.wikipedia.org/wiki/Convergent_%28continued_fraction%29

$11^2=121\equiv 4\pmod{13}$

$11^3\equiv4\cdot 11\equiv 5$

$11^4=(11^2)^2\equiv 4^2=16\equiv 3$

$11^5\equiv3\cdot11=33\equiv 7$

$11^6\equiv7\cdot 11= 77=-1$

$\implies 11\cdot 11^5\equiv-1\implies (11)^{-1}\equiv -11^5\equiv -7\equiv 6\pmod{13}$

$11^2=121\equiv 4\pmod{13}$

$11^3\equiv4\cdot 11\equiv 5$

$11^4=(11^2)^2\equiv 4^2=16\equiv 3$

$11^5\equiv3\cdot11=33\equiv 7$

$11^6\equiv7\cdot 11= 77=-1$

$\implies 11\cdot 11^5\equiv-1\implies (11)^{-1}\equiv -11^5\equiv -7\equiv 6\pmod{13}$

Alternatively, using [convergent][1] property of continued fraction,

$\frac{13}{11}=1+\frac 2{11}=1+\frac1{\frac{11}2}=1+\frac1{5+\frac12}$

So, the last but one convergent is $1+\frac15=\frac 6 5$

So, $11\cdot 6-13\cdot 5=66-65=1\implies 11\cdot 6\equiv 1\pmod{13}$ $\implies (11)^{-1}\equiv 6\pmod{13}$ [1]: http://en.wikipedia.org/wiki/Convergent_%28continued_fraction%29

Source Link
lab bhattacharjee
lab bhattacharjee
  • 280k
  • 20
  • 213
  • 338

$11^2=121\equiv 4\pmod{13}$

$11^3\equiv4\cdot 11\equiv 5$

$11^4=(11^2)^2\equiv 4^2=16\equiv 3$

$11^5\equiv3\cdot11=33\equiv 7$

$11^6\equiv7\cdot 11= 77=-1$

$\implies 11\cdot 11^5\equiv-1\implies (11)^{-1}\equiv -11^5\equiv -7\equiv 6\pmod{13}$