Varför är a mod b < a/2 (a>b)?

Hej,

Nu vill jag inte utelämna information: men lite bakgrund som jag inte tror är relevant alls för min fråga. Jag höll på med en uppgift som bad mig analysera tidskomplexiteten (datalogiskt begrepp) av $\text{gcd}(a,b)$ , implementerad m.h.a. Euklides algorithm.

Här visade sig en trivial egenskap (för att förstå uppgiften) vara att $a \mod b < \frac a 2$ .

Dessvärre kan jag inte hitta någon förklaring på internet som jag begriper, riktigt.

Jag tänker så här:

Antag att $a \mod b \le \frac a 2$ .

$a \mod b \iff a-qb$ där $q$ är en konstant, $qb \le a$

Alltså, antagandet blir

$a - qb \le \frac a 2$

$a(1-qb) \le \frac a 2$

Okej, nu får vi väl säga att $a$ inte är noll då, så det här blir inte superbra. Vi delar med $a$ iallafall:

$1-qb \le \frac 1 2$

$-qb \le - \frac 1 2$

$qb \ge 1$ .

Och här vill man säga typ "det gäller alltid", fanns jag vet inte om det stämmer...

Så det här säger inte heller någonting riktigt. Jag tror inte heller det är helt rätt på andra steg.

Finns det någon som kan ge mig en bra förklaring på hur det funkar?

Ni är hjältar!

Jag antar i detta inlägg att du menar att $a \operatorname{mod} b$ returnerar det minsta positiva heltalet som $a$ är kongruent med.

Vi kan tämka såhär:

Vi vet att $0\leq a \operatorname{mod} b < b$ .

Om $a \geq 2b$ är olikheten uppenbar eftersom $\frac a2 \geq b$ , vilket är större än vad modulo operatorn kommer returnera.

Därmed kan vi anta att $b<a<2b$ och då kan vi skriva $a = b+r$ , där $0<r<b$

Definitionen av modulo ger oss att $a \operatorname{mod} b = r$

Och vi har även att

$\displaystyle \frac{a}2 = \frac{b+r}{2} \underbrace{>}_{b > r} \frac{r+r}2 = \frac {2r}2 = r$

Alltså har vi att $a \operatorname{mod} b = r < \frac a2$

Jag kan förklara det med ord.

Om b<a/2 så kommer b att ”gå en gång till” i a. Vi kan alltså subtrahera b från a tills b>=a/2.
7 mod 3=1 eftersom 3 går två gånger i 7, med 1 som rest.

Om b=a/2 så är resten 0.

Om b>a/2 så kan måste resten vara <a/2.

Inte briljant matematiskt, men jag förstår hur jag tänker och som gammal kodare har jag alltid vetat att det är så utan att fundera så mycket.

Är a > b?

Laguna skrev:
Är a > b?

Det var det jag också undrade, det står i titeln. (Inte i inlägget)

AlexMu skrev:
Laguna skrev:
Är a > b?

Det var det jag också undrade, det står i titeln. (Inte i inlägget)

Ja titta.

AlexMu skrev:
vi har även att

$\displaystyle \frac{a}2 = \frac{b+r}{2} \underbrace{>}_{b > r} \frac{r+r}2 = \frac {2r}2 = r$

Alltså har vi att $a \operatorname{mod} b = r < \frac a2$

Den där delen var briljant, det var precis vad jag saknade.

Tack till dig och alla ni andra också förstås!

Sorry att jag glömde nämna a>b i OP.

Svara

Visa senaste svar