MaA 11 Talteori och bevis

5. Kongruens

Vilken veckodag

  1. är det om 4 dygn?
  2. är det om 18 dygn?
  3. var det för 17 dygn sedan?

Lösning

  1. Om det idag är måndag så är det om 4 dygn fredag.
  2. Eftersom veckan består av 7 dygn är det om 18 dygn samma dag som om \( 18 -7 \dot 2 = 4 \) dygn.
  3. För 17 dyng sedan var det samma dag som för \( 17 - 7\cdot 2 = 3 \) dygn sedan. Är det måndag idag var det för 3 dygn sedan fredag.

Vi märker att talen 18 och 4 har samma egenskaper kring delbarhet med talet 7. Inom matematiken talar vi om kongruens.

Anta att \( n \) är ett heltal som är större än 1. Heltalen \( a \) och \( b \) är kongruenta modulo \( n \) om deras differens är delbar med talet \( n \).

Om talen \( a \) och \( b \) kongruenta modulo \( n \), betecknar vi det med \( a \equiv b \quad (\mod n) \).

För våra tal gäller \( 18 - 4 = 14 \) och \( 14 \) är delbart med 7. Alltså \( 18 \equiv 4 \quad (\mod 7) \).

Exempel 1 Visa att

  1. \( 48 \equiv 13 \quad (\mod 7) \)
  2. \( -6 \equiv 12 \quad (\mod 3) \)

Lösning

  1. Eftersom \( 48 \equiv 13 \quad (\mod 7) \) betyder det att \( 48 - 13 = 35 = 7 \cdot 5 \)

    Alltså är \( 48 \equiv 13 \quad (\mod 7) \).

  2. Eftersom \( -6 \equiv 12 \quad (\mod 3) \) betyder det att \( -6 -12 = -18 = 3(-6) \).

    Alltså är \( -6 \equiv 12 \quad (\mod 3) \).

Egenskaper för kongruens

Kongruens har följande egenskaper. Vi antar att \( a \equiv b \quad (\mod n) \) och \( c \equiv d \quad (\mod n) \) och \( k \) är ett positivt heltal. Då gäller

  • \( a + c \equiv b + d \quad (\mod n) \)
  • \( ac \equiv bd \quad (\mod n) \)
  • \( a^k \equiv b^k \quad (\mod n) \)

Exempel 2 Visa att \( 2^{2020} -1 \) är delbart med 5.

Lösning

Eftersom \( 2^4 = 16 \) gäller att \( 2^4 \equiv 1 \quad (\mod 5) \).

Då får vi \( 2^{2020} = 2^{4\cdot 505} \equiv 1^{505} \quad (\mod 5) \).

Alltså gäller att \( 2^{2020} \equiv 1 \quad (\mod 5)\). Då gäller att \( 2^{2020}-1 \equiv 0 \quad (\mod 5) \).

Alltså är \( 2^{2020} -1 \) delbart med 5.

Exempel 3 Bestäm sista siffran i talet \( 2^{128} \).

Lösning

Vi börjar med att märka att \( 2^5 = 32 \equiv 2 \quad (\mod 10) \).

Vi kommer också behöva att \( 2^3 = 8 \equiv 8 \quad (\mod 10) \).

Sedan får vi att

\( \begin{array}{rcll} 2^{128} & = & 2^{5 \cdot 25 + 3} = 2^{5 \cdot 25} \cdot 2^3 \\ & \equiv & 2^{25} \cdot 2^3 = 2^{5 \cdot 5} \cdot 2^3 \\ & \equiv & 2^{5} \cdot 2^3 \\ & \equiv & 2 \cdot 8 = 16 \\ & \equiv & 6 \quad (\mod 10) \\ \end{array} \)

Det betyder att den sista siffran är 6.

Uppgifter

  1. Visa att
    1. \( 18 \equiv 6 \quad (\mod 3) \)

      \( 18 \equiv 6 \quad (\mod 3) \) eftersom \( 18 - 6 = 12 = 3 \cdot 4 \).

    2. \( 210 \equiv 147 \quad (\mod 7 ) \)

      \( 210 \equiv 147 \quad (\mod 7 ) \) eftersom \( 210 - 147 = 63 = 7 \cdot 9 \).

    3. \( 29 \equiv -6 \quad (\mod 5 ) \)

      \( 29 \equiv -6 \quad (\mod 5 ) \) eftersom \( 29 - (-6) = 35 = 5 \cdot 7 \)

  2. Visa att följande tal har samma rest då de divideras med samma tal.
    1. Talen 364 och 294 divideras med 7.

      Vi får att \( 364 - 294 = 70 = 7 \cdot 10 \)

      Alltså gäller \( 364 \equiv 294 \quad (\mod 7) \).

    2. Talen 754 och 421 divideras med 3.

      Vi får att \( 754 - 421 = 333 = 3 \cdot 111 \)

      Alltså gäller \( 754 \equiv 421 \quad (\mod 3) \).

    3. Talen 666 och 380 divideras med 11.

      Vi får att \( 666 - 380 = 286 = 11 \cdot 26 \)

      Alltså gäller \( 666 \equiv 380 \quad (\mod 11) \).

  3. Visa att
    1. \( 3^5 \equiv 3 \quad (\mod 5) \)

      Vi kan visa på följande sätt \( 3^5 \equiv 3 \quad (\mod 5) \) betyder att \( 3^5 - 3 = 243 -3 = 240 = 5 \cdot 48 \)

    2. \( 2^{20} \equiv 1 \quad (\mod 33) \)

      Vi kan visa på följande sätt: \( 2^{20} \equiv 1 \quad (\mod 33) \) betyder att \( 2^{20} - 1 = 1048575 = 33 \cdot 31775 \).

      Jobbar vi med större tal blir det problem. Då måste vi tänka som följande.

      Problemet är \( \mod 33 \), vi skall då hitta tal som är delbara med 33. Men eftersom \( 33 = 3\cdot 11 \) så visar vi att \( 2^{20} \equiv 1 \quad (\mod 3) \) och \( 2^{20} \equiv 1 \quad (\mod 11) \)

      Eftersom \( 2^2 \equiv 1 \quad (\mod 3) \) får vi att \( 2^{20} = (2^{10})^2 \equiv 1^{10} \equiv 1 \quad (\mod 3) \).

      Dessutom gäller att \( 2^5 = 32 \equiv -1 \quad (\mod 11) \) får vi att \(2^{20} = (2^5)^4 \equiv (-1)^4 \equiv 1 \quad (\mod 11) \).

    3. \( 7^{12} \equiv 1 \quad (\mod 48 ) \)

      \( 7^{12} \) är ett såpass stort tal att vi kan inte direkt räkna ut dess värde.

      Vi märker att \( 48 = 4 \cdot 12 \). Vi tar och visar att \( 7^{12} \equiv 1 \quad ( \mod 4 ) \) och att \( 7^{12} \equiv 1 \quad (\mod 12 ) \).

      Eftersom \( 7^2 = 49 \equiv 1 \quad (\mod 4) \) får vi att \( 7^{12} = (7^6)^2 \equiv 1^6 \equiv 1 \quad (\mod 4) \).

      Dessutom gäller att \(7^2 \equiv 1 \quad (\mod 12) \). Då får vi \( 7^{12} = (7^6)^2 \equiv 1^6 \equiv 1 \quad ( \mod 12 ) \).

  4. Visa att talet \( 2^{342} -1 \) är delbart med 7.

    Eftersom \( 2^3 = 8 \) är \( 2^3 \equiv 1 \quad (\mod 7) \).

    Då gäller att \( (2^3)^{k} = 2^{3k} \equiv 1 \quad (\mod 7) \).

    Eftersom \( 342 = 3 \cdot 114 \) gäller att \( 2^{342} = 2^{2 \cdot 114 } \equiv 1^{114} \quad (\mod 7) \).

    Eftersom \( 2^{342} \equiv 1 \quad (\mod 7) \) får vi att \( 2^{342} -1 \equiv 0 \quad (\mod 7) \). Detta betyder att \( 2^{342} -1 \) är delbart med 7.

  5. Visa att talet \( 2^{800} -1 \) är delbart med talet 341.

    Vi faktoriserar \( 341 = 31 \cdot 11 \).

    Vi skall visa att \( 2^{800} \equiv 1 \quad (\mod 11) \) och \( 2^{800} \equiv 1 \quad (\mod 31) \)

    Vi har \( 2^5 \equiv 1 \quad (\mod 31) \). Vi jobbar med uttrycket \( (2^5)^2 \equiv 1^2 \quad (\mod 31) \), alltså \( 2^{10} \equiv 1^2 \quad (\mod 31) \).

    Dessutom har vi \( 2^5 \equiv -1 \quad (\mod 11) \) får vi att \( (2^5)^2 \equiv (-1)^2 \quad (\mod 11) \), alltså \( 2^{10} \equiv 1 \quad (\mod 11) \).

    Då vi kombinerar får vi att \( 2^{800} = (2^{10})^{80} \equiv 1 \quad (\mod 341) \).

  6. Bestäm sista siffran i talet \( 2^{99} \).

    Först märker vi att \( 2^5 = 32 \equiv 2 \quad (\mod 10) \).

    Sedan får vi att

    \( \begin{array}{rcll} 2^{99} & = & 2^{5 \cdot 19} \cdot 2^4 \\ & \equiv & 2^{19} \cdot 2^4 = 2^{23} = 2^{5\cdot 4} \cdot 2^3 \\ & \equiv & 2^4 \cdot 2^3 = 16 \cdot 8 \\ & \equiv & 6 \cdot 8 \quad(\mod 10) & | 6\cdot 8 = 48 \\ & \equiv & 8 \quad(\mod 10) \\ \end{array} \)

    Den sista siffran är 8.

  7. Bestäm sista siffran i talet \( 3^{224} \).

    Vi börjar med att märka att \( 3^4 = 81 \equiv 1 \quad(\mod 10) \).

    Sedan får vi att

    \( \begin{array}{rcll} 3^{244} & = & 3^{4\cdot 61} = 3^{4 \cdot 60} \cdot 3 \\ & \equiv & 3^{60} \cdot 3 = 3^{4 \cdot 15} \cdot 3 \\ & \equiv & 3^{15} \cdot 3 = 3^{16} = (3^4)^2 \\ & \equiv & 1 \quad (\mod 10) \\ \end{array} \)

    Den sista siffran är 1.

  8. Bestäm sista siffran i talet \( 5^{1234} \).

    Efter lite räknande märker vi att

    \( 5^2 = 25 \equiv 5 \quad (\mod 10) \)

    \( 5^3 = 125 \equiv 5 \quad (\mod 10) \)

    \( 5^4 = 625 \equiv 5 \quad (\mod 10) \)

    \( 5^5 = 3125 \equiv 5 \quad (\mod 10) \)

    Vi kommer behöva alla dessa, man märker det när vi räknar på.

    Sedan får vi att

    \( \begin{array}{rcll} 5^{1234} & = & 5^{2 \cdot 617} \\ & \equiv & 5^{617} = 5^{5 \cdot 123 + 2} = 5^{5 \cdot 123} \cdot 5^2 \\ & \equiv & 5^{123} = 5^{3 \cdot 41} \\ & \equiv & 5^{41} = 5^{4 \cdot 8 + 1} = 5^{4 \cdot 8} \cdot 5 \\ & \equiv & 5^{8} \quad(\mod 10) \\ \end{array} \)

    Den sista siffran är 5. Senare med hjälp av induktion kommer vi visa att alla potenser med basen 5 slutar med talet 5.

  9. Bestäm sista siffran i talet \( 7^{2018} \).

    Här använder vi oss av olika tals kongruens.

    \( 7 \equiv 3 \quad (\mod 10) \)

    \( 9 \equiv -1 \quad (\mod 10) \)

    Sedan får vi att

    \( \begin{array}{rcll} 7^{2018} & \equiv & (-3)^{2018} \\ & \equiv & ((-3)^2)^{1009} = 9^{1009} \\ & \equiv & (-1)^{1009} = -1 \\ & \equiv & 9 \quad (\mod 10) \\ \end{array} \)

    Den sista siffran är 9.