Citat:
	
		
			
			
				 Ursprungligen postat av 
Finoli
			 
			Jag har följande uppgift:
Bestäm resten då 3^129 delas med 5. Förklara vad du gör på ett tydligt men kortfattat sätt.
Nehöver en förklaring och inte bara en massa siffror som bara krånglar till det i huvet för mig. Anyone up for it?
		
	 
 
Man löser sådana här uppgifter genom modulo-räkning, vilket bygger på att om ett visst tal x ger en viss rest r vid division med ett annat tal y så kommer n*x att ge resten n*r vid division med y om n är ett heltal. Detta är egentligen ganska naturligt; om x ger resten r vid division med y innebär det att x = k*y + r för något heltal k. Således är n*x = n*(k*y + r) = n*k*y + n*r, där n*k*y uppenbart är jämnt delbart med y eftersom både n och k är heltal.
I ditt fall så har du 3¹²⁹ och skall finna resten vid division med 5. Tänk då på att 3⁴ = 81, som uppenbart ger resten 1 vid division med 5. Således kommer resten då 3¹²⁹ = 3⁴*3¹²⁵ divideras med 5 att vara detsamma som resten då 3¹²⁵ divideras med 5 gånger resten då 3⁴ = 81 divideras med 5, dvs resten då 3¹²⁵ divideras med 5 gånger 1 eller alltså helt enkelt resten då 3¹²⁵ divideras med 5.
Detta kan du göra om upprepade gånger genom att gång på gång bryta ut en faktor 3⁴ = 81. Resten då 3¹²⁹ divideras med 5 är samma som resten då 3¹²⁵ divideras med 5, vilket är samma som resten då 3¹²¹ divideras med 5, och så vidare. Du subtraherar 4 från exponenten upprepade gånger och kommer i slutändan fram till att resten blir detsamma som då 3¹ divideras med 5, vilket naturligtvis blir 3.