Diskret matematik uppgift 1a)

Ska du använda Eulers teorem?
I detta fall behöver du beräkna $\phi \left(7\right)$ som är 6.

Hjälper det?

Macilaci skrev:

Ska du använda Eulers teorem?
I detta fall behöver du beräkna $\phi \left(7\right)$ som är 6.

Hjälper det?

Vi har ej gått igenom eulers teorem.  Känner ej igen det tyvärr

Annars kan man skriva upp en tabell med resterna:

Ser du betydelsen av nummer 6?

10⁰ _mod(7) = 10⁶_mod(7) = 10¹²_mod(7) = osv

Macilaci skrev:

Annars kan man skriva upp en tabell med resterna:

1	1
10	3
100	2
1000	6
10000	4
100000	5
1000000	1
...	...

Ser du betydelsen av nummer 6?

10⁰ _mod(7) = 10⁶_mod(7) = 10¹²_mod(7) = osv

Jag ser ingenting tyvärr.  Blir bara förvirrad av tabellen och alla tio som ökar. Finns det andra sätt?

Resterna upprepar sig. 

Detta beror på reglerna för modulär multiplikation:

a_mod(x) * b_mod(x) = (a*b)_mod(x)

I vårt fall:

10⁰ _mod(7) = 10⁶_mod(7) = 10¹²_mod(7) = ... = 10⁹⁹⁶_mod(7)

Macilaci skrev:

Detta beror på reglerna för modulär multiplikation:

a_mod(x) * b_mod(x) = (a*b)_mod(x)

I vårt fall:

10⁰ _mod(7) = 10⁶_mod(7) = 10¹²_mod(7) = ... = 10⁹⁹⁶_mod(7)

Okej nu är jag ännu mer vilse

Om du kollar tiopotenser (1, 10, 100, 1000...), har var sjätte tiopotens samma rest vid division med 7.

T.ex.

1_mod(7) = 1

1 000 000_mod(7) = 1

1 000 000 000 000_mod(7) = 1

Macilaci skrev:

Om du kollar tiopotenser (1, 10, 100, 1000...), har var sjätte tiopotens samma rest vid division med 7.

Jag förstår ej riktigt.  Jag får återkomma när jag pratat med dem på livehjälp.

(10)_mod(7) = 10_mod(7) * 1_mod(7) = 3

(10 000 000)_mod(7) = 10_mod(7) * 1 000 000_mod(7) = 3

(10 000 000 000)_mod(7) = 10_mod(7) * 1 000 000 000_mod(7) = 3

...osv

Det betyder att du kan fortsätta tabellen godtyckligt utan att behöva beräkna alls:

Resterna av tiopotenser är: 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3,...

Macilaci skrev:

(10)_mod(7) = 10_mod(7) * 1_mod(7) = 3

(10 000 000)_mod(7) = 10_mod(7) * 1 000 000_mod(7) = 3

(10 000 000 000)_mod(7) = 10_mod(7) * 1 000 000 000_mod(7) = 3

...osv

Det betyder att du kan fortsätta tabellen godtyckligt utan att behöva beräkna alls:

Resterna av tiopotenser är: 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3,...

Jag kom på att resten är 3 när vi delar 10 med 7. Vi har ju a =b mod(n). Betyder det att 10^1 osv har också rest 3?

Jag skriver kanske lite konstigt, jag använde inte vanlig notation.

När jag skrev 10_mod(7) betydde det resten av 10 delat med 7 (som är 3 som är lika med 10 i mod(7) räkning).

Jag borde ha skrivit så här:

$$\begin{gathered} 10\equiv 3 mod\left(7\right) \\ 100 \equiv 10*10 \equiv 3*3 \equiv 9 \equiv 2 mod\left(7\right) \\ 1000 \equiv 100*10 \equiv 2*3 \equiv 6 mod\left(7\right) \\ 10 000 \equiv 1000*10 \equiv 6*3\equiv 18\equiv 4 mod\left(7\right) \\ 100 000 \equiv 10 000*10 \equiv 4*3 \equiv 12 \equiv 5 mod\left(7\right) \\ 1 000 000 \equiv 100 000*10 \equiv 5*3 \equiv 15 \equiv 1 mod\left(7\right) \\ 10 000 000 \equiv 1 000 000*10 \equiv 1*3 \equiv 3 mod\left(7\right) \\ ... \end{gathered}$$

Kan vi gå igenom facits lösning?

• Var kommer 2^500 ifrån?
• Var kommer 1*4 mod(7) ifrån?

$9 \equiv 2 (\mod 7)$, alltså är $9^{500} \equiv 2^{500} (\mod 7)$.

Laguna skrev:

$9 \equiv 2 (\mod 7)$, alltså är $9^{500} \equiv 2^{500} (\mod 7)$.

Okej men andra punkten då?

$8 \equiv 1 (\mod 7)$.

Laguna skrev:

$8 \equiv 1 (\mod 7)$.

Ok jag förstår ej hur de kom fram till denna?

500=3*166+2. Jag hade istället tänkt (2^2)^250

När du håller på med modulo-räkning så vill du gärna ta fram tal som är kongruenta med 1, för om man upphöjer dem till något så blir "de nya talen" också kongruenta med 1. Om man inte kan hitta detta, så är det nästan lika bra med tal som är kongruenta med -1, för de är antingen kongruenta med 1 eller med -1 beroende på om man upphöjer till jämnt eller udda tal. 8 är kongruent med 1 (modulo 7) så det är ett tal som underlättar. 4 är kongruent med 4, så det hjälper oss inte vidare.

Smaragdalena skrev:

När du håller på med modulo-räkning så vill du gärna ta fram tal som är kongruenta med 1, för om man upphöjer dem till något så blir "de nya talen" också kongruenta med 1. Om man inte kan hitta detta, så är det nästan lika bra med tal som är kongruenta med -1, för de är antingen kongruenta med 1 eller med -1 beroende på om man upphöjer till jämnt eller udda tal. 8 är kongruent med 1 (modulo 7) så det är ett tal som underlättar. 4 är kongruent med 4, så det hjälper oss inte vidare.

Hur menar du 4 är konguent med 4?

Vad har 4 för rest när man delar det med 7? (Kvoten är 0 i detta fall.)

Även 11, 18 och 25 är kongruenta med 4 modulo 7, men med andra värden på kvoten.

Smaragdalena skrev:

Vad har 4 för rest när man delar det med 7? (Kvoten är 0 i detta fall.)

Även 11, 18 och 25 är kongruenta med 4 modulo 7, men med andra värden på kvoten.

Jag får 4=7*1-3. Resten är -3. Jag vet ej vad du menar med kvoten 0.

4 delat med 7 går inte, det är för lite, så kvoten är 0. Resten är 4.

Om vi inte räknar modulo: 4/7 = 0,57142857142857142857142857142857... d v s kvoten är mindre än 1.

Men om du menar att även -3 är kongruent med 4 modulo 7 så har du helt rätt.

Smaragdalena skrev:

4 delat med 7 går inte, det är för lite, så kvoten är 0. Resten är 4.

Om vi inte räknar modulo: 4/7 = 0,57142857142857142857142857142857... d v s kvoten är mindre än 1.

Men om du menar att även -3 är kongruent med 4 modulo 7 så har du helt rätt.

"Men om du menar att även -3 är kongruent med 4 modulo 7 så har du helt rätt" 

Nja jag menade kanske ej så även om detta är sant. Men då är det altltså fel att säga 4 är konguent med -3 modulo 7 för att 4 går ej att dela med 7? Ska täljaren alltså vara större än nämnaren för att divison ska utföras?

Det verkar som om du behäver repetera vad som menas med moduloräkning.