Vi letar efter det minsta naturliga talet $x$ som uppfyller två kongruenser:

$x \equiv 1 \,(\text{mod}\, 83)$ $x \equiv 3 \,(\text{mod}\, 47)$

För att lösa detta använder vi den kinesiska restklassatsen, som kan användas för att lösa system av kongruenser när moduli är inbördes relativt prima. Eftersom $83$ och $47$ är relativt prima (deras största gemensamma delare är 1), kan vi applicera metoden.

Steg 1: Ställ upp ekvationerna

Vi har: x = 83k + 1 \quad \text{(för något heltal k)} Sätt detta uttryck för $x$ i den andra kongruensen: $83k + 1 \equiv 3 \,(\text{mod}\, 47)$ $83k \equiv 2 \,(\text{mod}\, 47)$

Steg 2: Reducera $83 \mod 47$

Beräkna $83 \mod 47$: $83 \equiv 36 \,(\text{mod}\, 47)$ Nu har vi ekvationen: $36k \equiv 2 \,(\text{mod}\, 47)$

Steg 3: Lös den diofantiska ekvationen

Vi behöver nu hitta $k$ som löser: $36k \equiv 2 \,(\text{mod}\, 47)$ För detta behöver vi hitta den inversa av $36$ mod $47$. Detta kan göras med hjälp av Euklides algoritm.

Låt oss köra Euklides algoritm för att hitta den multiplikativa inversen av $36$ modulo $47$.Den inversa av $36$ mod $47$ är $17$.

Steg 4: Lös för $k$

Nu multiplicerar vi båda sidor av ekvationen $36k \equiv 2 \,(\text{mod}\, 47)$ med $17$:

$k \equiv 2 \cdot 17 \,(\text{mod}\, 47)$ $k \equiv 34 \,(\text{mod}\, 47)$

Steg 5: Beräkna $x$

Nu när vi har $k = 47m + 34$ (för något heltal $m$), kan vi sätta detta i uttrycket för $x$: $x = 83k + 1 = 83(47m + 34) + 1$ $x = 3901m + 2823 + 1 = 3901m + 2824$

Så det minsta värdet på $x$ är när $m = 0$, vilket ger: $x = 2824$

Det minsta naturliga talet som uppfyller båda kongruenserna är alltså $x = 2824$.

Vill du ha fler detaljer eller har du några frågor?

Här är några relaterade frågor:

1. Hur fungerar den kinesiska restklassatsen?
2. Kan vi lösa detta problem med en annan metod?
3. Vad är Euklides algoritm och hur tillämpas den här?
4. Hur fungerar multiplikativ invers i modulär aritmetik?
5. Vad betyder det att två tal är relativt prima?

Tips: När du löser kongruenssystem kan den kinesiska restklassatsen vara mycket användbar, särskilt om moduli är relativt prima.