gcd の公式

gcd は greatest common devisor の略で最大公約数を表します.この記号は非常に強力なツールです.余り浸透しているとは言い難いので今回はこの記号を使って公式化して置きたい事項を話す事にします.

a, n が互いに素 ⇔ gcd (a, n) = 1
同値な事に注意して下さい.

gcd (ka, kb) = k・gcd (a, b)
共通な因数は括れます.

gcd (tα+uβ, β) = gcd (tα, β)
ユークリッドの互除法ですね.
gcd (a, b) = gcd (a+b, b) = gcd (a-b, b)
= gcd (a, b+a) = gcd (a, b-a)

なんかもそうです.

ユークリッドの互除法を繰り返した後の形では,
gcd (d, 0) = d
gcd (d, 1) = 1

が重要です.

縦棒線を用いた割り切る記号と共に併用した物として重要なのは,
a | x, a | y ⇒ a | gcd (x, y)
a | x, b | x ⇒ lcm (a, b) | x

です.lcm は lowest common multiple (最小公倍数) です.
割り切ると言う記号の性質上,
x | y ⇒ |x| ≤ |y|
なので,左側は lcm で大きな数に,右側は gcd で小さな数に成る事を意識して置けばこの 2つを混同する事は無いと思います.
実はこの 2つを使うと明快な答案に成る京大の過去問が有り,原稿はもう出来上がっているのですが,入試で使って良いかどうか分から無いので参考程度に見て下さい.

Post a comment

Private comment

プロフィール

A6033x

Author:A6033x
数検1級取得しました.
個人的な連絡は,hermitvseinsiedler@_@gmail.com
まで(@_@は@に置換すること).
あまり見ないかも知れないのでその場合は twitter の方へ.
twitter:https://twitter.com/A603zw
そもそもネット接続自体減らして行く事になりますが...

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR