2．条件式(オイラー関数）

条件式の例と意味

C言語では, 式の値が０のとき偽, ０以外は真であると解釈される

条件式	内容
( a == b )	aとbが等しい. 等号（=） 2つであることに注意
( a < b )	bがaより大きい
( a > b )	aがbより大きい
( a <= b )	bがaより大きいか，等しい　=< とは書か（け）ない.
( a >= b )	aがbより大きいか，等しい　 => とは書か（け）ない.
( a != b )	aとbが等しくない
(a>b && b>c)	a>b　かつ b>c　　注：これを（a>b>c)とは書いてはダメ
(a>b || b>c)	a>b または b>c
(!(a>b && c==d))	「a>b　かつ c==d」でない　（!は否定を表す）
int n ; ・・・・・ if (n%3) {・・・	整数nを３で割った余りが０以外

条件式 a == b を書くつもりで, 代入式 a = b を書いてしまうことはよくやる間違いです.

例.

• a,b,n を正整数とする. n % a == 0 && n % b == 0 　⇔ 「a,b の最小公倍数は n を割り切る」
• p を奇素数, i を p-1 以下の正整数とする. 「i は　p-1 か (p-1)/2 」 ⇔ (i == p-1 || i == (p-1)/2)
• p,q素数とする. n はpq以下の正整数とする. 「n と pq は互いに素」　⇔ (n % p != 0 && n % q !=0 )

問

1. p,q を異なる素数とする. pq と互いに素な, pq以下の正整数の個数を求めよ. p=29, q=41 の場合の具体的な個数
2. p を素数, e を正整数とする. p^e と互いに素な, p^e 以下の正整数の個数

この問題はオイラー関数と関連しています. オイラー関数の詳しい表示はここを見てください. また教科書の64頁も見て下さい.

参考文献

• ジョセフ・H・シルヴァーマン, はじめての数論 原著第3版 (発見と証明の大航海ーーピタゴラスの定理から楕円曲線まで） , ピアソン・エデゥケーション, 2007. 第11章.
  ジョセフ・H・シルヴァーマンはNTRU暗号を1998年に提案した, 数論学者です.

Ｃ言語　　　　　　　反復処理
プログラ　　　　　　（原始根)
ミングの
基礎(合同式)