---
# System prepended metadata

title: 模運算0
tags: [數學]

---

---
tags: 數學
title: 模運算0
---

# Mod 性質

:::success
## MOD 運算性質
- 假設 a,b，a,b都是整數
- 假設 c（運算結果），是非負整數
### 加法
- $c = (a + b)\%m = (a\%m + b\%m) \% m$
### 減法
- $c = (a - b)\%m = ((a\%m - b\%m)\%m +m)\%m$
- 不過建議這樣寫
    - if $a\%m-b\%m >= 0$ ，$c = (a - b)\%m = (a\%m - b\%m)\%m$
    - if $a\%m-b\%m < 0$ ，$c = (a - b)\%m = (a\%m - b\%m)\%m + m$
### 乘法
- $c = (a * b)\%m = (a\%m * b\%m)\% m$
### 除法
- $c = (a / b)\%m =$ [參考--模逆元](https://hackmd.io/MBrsyQ4ySKuGSNb7RGR0fg?both)
### 萬能公式
- $a\%m = a - \lfloor \frac{a}{m} \rfloor \times m$
:::

:::success
## GCD, LCM
- 最大公因數
- $gcd(a,b) = gcd(b, a\%b)$
- $a * b = gcd(a,b) * lcm(a,b)$
:::