MaA 11 Talteori och bevis

11. Repetition

Uppgifter

  1. Ange elementen i följande mängder.
    1. \( A = \{ x \in \mathbf{Z} \mid x < 6 \} \)

      Vi får \( A = \{ \ldots, 3,4,5,6 \} \).

    2. \( B = \{ x \in \mathbf{N} \mid x < 6 \} \)

      Vi får \( B = \{ 0,1,2,3,4,5,6 \} \).

    3. \( C = \{ x \in \mathbf{R}: \mid x \mid \leq 3 \} \)

      Vi får \( C = \{ -3, \ldots, 3 \} \).

      Alla reella tal vars avstånd till 0 är mindre än 3.

  2. Låt talmängderna vara samma som i förra uppgiften. Bilda följande mängder.
    1. \( A \cup B \)

      Vi får \( \{ \ldots,2,3,4,5,6 \} \).

    2. \( A \cap B \)

      Vi får \( \{ 0,1,2,3,4,5,6 \} \).

    3. \( B \cap C \)

      Vi får \( \{ 0,1,2,3 \} \).

  3. Omvandla följande tal till den angivna talbasen.
    1. \( 64_{7} \) i basen 10.

      Vi får \( 6 \cdot 7^1 + 4 \cdot 7^0 = 46 \).

    2. \( 36_{10} \) i basen 5.

      Vi får

      \( \begin{array}{rcl} 36 / 5^2 & = & 1 \text{ rest } 11 \\ 11 / 5^1 & = & 2 \text{ rest } 1 \\ 1 / 5^0 & = & 1 \text{ rest } 0 \\ \end{array} \)

      Alltså \( 36_{10} = 121_{5} \).

    3. \( 34_{4} \) i basen 9.

      Vi går via basen 10.

      \( 34_{4} = 3 \cdot 4^1 + 4 \cdot 4^0 = 16_{10} \).

      Sedan får vi

      \( \begin{array}{rcl} 16_{10} / 9^1 & = & 1 \text{ rest } 7 \\ 7 / 9^0 & = & 7 \text{ rest } 0 \\ \end{array} \)

      Alltså \( 34_{4} = 17_{9} \).

  4. Faktorisera följande tal till primtalsfaktorer.
    1. 68

      \( 68 = 2^2 \cdot 17 \).

    2. 64350

      \( 64350 = 2 \cdot 3^2 \cdot 5^2 \cdot 11 \cdot 13 \).

    3. 15369

      \( 15369 = 3 \cdot 47 \cdot 109 \)

  5. Bestäm för talen 68 och 64350 deras strösta gemensamma faktor genom att utnyttja primtalsuppdelningen och Euklides algoritm.

    Primtalsuppdelningen ger SGF(68,64350) = 2.

    Euklides algoritm ger

    \( \begin{array}{rcl} 64350 / 68 & = & 946 \text{ rest } 22 \\ 68 / 22 & = & 3 \text{ rest } 2 \\ 22 / 2 & = & 11 \text{ rest } 0 \\ \end{array} \)

    Alltså är SGF(68,64350) = 2.

  6. Visa att följande kongruenser gäller.
    1. \( 7 \equiv 19 (\mod 3) \)

      \( 7 \equiv 19 (\mod 3) \) eftersom \( 7 - 19 = -12 = 3 \cdot (-4) \).

    2. \( -3 \equiv 19 (\mod 11) \)

      \( -3 \equiv 19 (\mod 11) \) eftersom \( -3 - 19 = -22 = 11 \cdot (-2) \).

    3. \( -3 \equiv 8 \equiv 19 (\mod 11) \)

      \( -3 \equiv 8 \equiv 19 (\mod 11) \) eftersom \( -3 - 8 = -11 = 11(-1) \), \( 8 -19 = -11 \) och \( -3 - 19 = -22 = 11 \cdot (-2) \).

  7. Lös följande diofantiska ekvationer.
    1. \( 2x + 3 y = 11 \)

      Med hjälp av divisionsalgoritmen får vi

      \( \begin{array}{rcl} 3 & = & 1 \cdot 2 + 1 \\ 2 & = & 2 \cdot 1 + 0 \\ \end{array} \)

      Alltså sgf(3,2)=1 och 1 är en faktor i 11.

      Sedan går vi baklänges och börjar med \( 1 = 3 - 2\cdot 1\). Vi jobbar vidare och kommer till \( 2 \cdot (-11) + 3 \cdot 11 = 11 \).

      Alltså är en lösning \( x = -11 \) och \( y = 11 \).

      Kandidaterna är \( x = -11 \pm 3 n \) och \( y = 11 \pm 2n \).

      Vi för lösningarna \( x = -11 + 3 n \) och \( y = 11 - 2n \).

    2. \( 35x + 80y = 36 \)

      Med hjälp av divisionsalgoritmen får vi

      \( \begin{array}{rcl} 80 & = & 2 \cdot 35 + 10 \\ 35 & = & 3 \cdot 10 + 5 \\ 10 & = & 2 \cdot 5 + 0 \\ \end{array} \)

      Alltså sgf(35,80)=5. Men 5 är inte en faktor i 36 så ekvationen saknar lösningar.

    3. \( 1332 x + 1032 y = 3600 \)

      Med hjälp av divisionsalgoritmen får vi

      \( \begin{array}{rcl} 1332 & = & 1 \cdot 1032 + 300 \\ 1032 & = & 3 \cdot 300 + 132 \\ 300 & = & 2 \cdot 132 + 36 \\ 132 & = & 3 \cdot 36 + 24 \\ 36 & = & 1 \cdot 24 + 12 \\ 24 & = & 2 \cdot 12 \\ \end{array} \)

      Alltså sgf(1332,1032)=12 och 12 är en faktor i \(3600 = 12 \cdot 300\).

      Sedan går vi baklänges och börjar med

      \( \begin{array}{rcl} 12 & = & 36 - 1 \cdot 24 \\ & = & 36 - 1 (132 - 3\cdot 36) \\ \end{array} \)

      Vi jobbar vidare och kommer till att \( 12 = 1332 \cdot 31 + 1032 (-40) \).

      Alltså är en lösning \( x = 300 \cdot 31 = 9300 \) och \( y = -40 \cdot 300 = -12000 \).

      Kandidaterna är \( x = 9300 \pm 1032 n \) och \( y = -12000 \pm 1332n \).

      Vi för lösningarna \( x = 9300 + 1032 n \) och \( y = -12000 - 1332n \).

  8. För vilka värden på A och B är följande logiska satser sanna?
    1. \( A \wedge B \Rightarrow A \vee B \)

      Vi får

      \( \begin{array}{|c|c|c|c|c|} \hline A & B & A \wedge B & A \wedge B \Rightarrow A & A \wedge B \Rightarrow A \vee B \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 \\ \hline 0 & 0 & 0 & 1 & 1 \\ \hline \end{array} \)

      Alltid sann, vi har en tautologi.

    2. \( (A \wedge B) \Rightarrow (A \vee B) \)

      Vi får

      \( \begin{array}{|c|c|c|c|c|} \hline A & B & A \wedge B & A \vee B & (A \wedge B) \Rightarrow (A \vee B) \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 & 1 \\ \hline \end{array} \)

      Alltid sann, vi har en tautologi.

    3. Visa att \( \neg(A \wedge B) \Leftrightarrow (\neg A \vee \neg B) \)

      Vi får

      \( \begin{array}{|c|c|c|c|} \hline A & B & A \wedge B & \underbrace{\neg(A \wedge B)}_{C} & \neg A & \neg B & \underbrace{\neg A \vee \neg B}_{D} & C \Leftrightarrow D \\ \hline 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \)

  9. Visa med induktion att \( 1 \cdot 2^0 + 2\cdot 2^1 + 3 \cdot 2^2 + \ldots + n \cdot 2^{n-1} = (n-1)2^{n} + 1 \) då \( n = 1,2,3,4,\ldots \).

    Grundsteget: Vi testar med \( n = 1 \). Vi får \( 1 \cdot 2^{1-1} = 1 \) och \( (1-1)2^{1} + 1 = 1 \).

    Formeln tycks stämma.

    Induktionssteget: Vi jobbar med \( k + 1 \).

    Vi skall komma fram till \( (k+1-1)2^{k+1} + 1 = k\cdot 2^{k+1} + 1 \).

    Vi får

    \( \begin{array}{rcl} 1 \cdot 2^0 + 2\cdot 2^1 + \ldots + k \cdot 2^{k-1} + (k+1) \cdot 2^{k+1-1} & = & (k-1)2^{k} + 1 + (k+1) \cdot 2^{k+1-1} \\ & = & (k-1)2^{k} + 1 + (k+1) \cdot 2^{k} \\ & = & 2^k \cdot (k-1+k+1) +1 \\ & = & 2^k \cdot 2k +1 \\ & = & k\cdot 2^{k+1} +1 \\ \end{array} \)

    Alltså stämmer formeln.

  10. Visa med hjälp av induktion att för alla \( n \in \mathbf{N} \) gäller att \( D x^n = nx^{n-1} \).

    Grundsteget: Vi testar med \( n = 0 \). Vi får \( Dx^0 = D 1 = 0 \) och \( 0 \cdot x^{n-0} = 0 \).

    Formeln tycks stämma.

    Induktionssteget: Vi jobbar med \( k +1 \).

    Vi skall visa att \( D x^{k+1} = (k+1)x^k \).

    Vi får

    \( \begin{array}{rcl} D x^{k+1} & = & D(xx^k) \\ & = & xDx^k + x^kDx \\ & = & xkx^{k-1} + x^k \cdot 1 \\ & = & kx^k + x^k \\ & = & (k+1)x^k \\ \end{array} \)

    Vilket är vad vi skulle visa. Formeln stämmer.

  11. Bestäm sista siffran i talet \( 2^{96} \).

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

    Sedan får vi att

    \( \begin{array}{rcll} 2^{96} & = & 2^{5 \cdot 19} \cdot 2 \\ & \equiv & 2^{19} \cdot 2 = 2^{5\cdot 4}\\ & \equiv & 2\cdot 2^4 = 2^5 \\ & \equiv & 2 \quad(\mod 10) \\ \end{array} \)

    Den sista siffran är 2.

  12. Bestäm sista siffran i talet \( 3^{313} \).

    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^{313} & = & 3^{4\cdot 78} \cdot 3 \\ & \equiv & 3^{78} \cdot 3 = 3^{4 \cdot 19 + 2} \cdot 3 = 3^{4 \cdot 19} \cdot 3^3 \\ & \equiv & 3^{19} \cdot 3^3 = 3^{4 \cdot 4 + 3} \cdot 3^3 = 3^{4 \cdot 4} \cdot 3^6 \\ & \equiv & 3^4 \cdot 3^6 \\ & \equiv & 1 \cdot 3^6 = 3^{4} \cdot 3^2 \\ & \equiv & 1 \cdot 3^2 = 1 \cdot 9 \quad (\mod 10) \\ \end{array} \)

    Den sista siffran är 9.

  13. Vilka av talen \( 111 111 111 \), \( 222 222 222 \) och \( 333 333 333 \) är delbara med talet nio?

    Är talet \( 111 111 111^{111 111 111} + 222 222 222^{222 222 222} + 333 333 333^{333 333 333} \) delbart med talet nio? Motivera ditt svar.

    Ett tal är delbart med 9 om siffersumman är delbart med 9.

    Siffersumman av 111 111 111 är 9, av talet 222 222 222 är 18 och av talet 333 333 333 är 27.

    Alla tre tal är delbara med 9.

    Om talet är delbart med 9 är också \( n^k \) delbart med 9, då \( k \) är ett positivt heltal.

    Alltså är \( 111 111 111^{111 111 111} \), \( 222 222 222^{222 222 222} \) och \( 333 333 333^{333 333 333} \) delbara med nio.

    Och summan av talen är delbart med 9.

    Detta är en gammal SE uppgift, hösten 2019 uppgift 8.

  14. Vi antar att \( p \) , \( q \) och \( r \) är positiva heltal. Visa att talet \( (p + q)(q + r)(r + p) \) är jämnt.

    Vi undersöker först det fall då minst 2 av talen \( p \) , \( q \) och \( r \) är jämna.

    Summan av två jämna tal är jämn, vilket betyder att produkten \( (p+q)(q+r)(r+p) \) är jämn.

    Vi undersöker sedan det fall då minst 2 av talen \( p \) , \( q \) och \( r \) är udda.

    Summan av två udda tal är jämn, vilket betyder att produkten \( (p+q)(q+r)(r+p) \) är jämn.

    Detta är en gammal SE uppgift, våren 2017 uppgift 9.