オイラーの定理

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
nana0627

オイラーの定理

#1

投稿記事 by nana0627 » 5年前

「互いに素である正の整数n,aに対して、n未満でnと互いに素である整数の個数をφ(n)としたとき、“a^{φ(n)} - 1はnで割り切れる”」
1以上50未満のnと1以上n未満でnと互いに素なaのすべての組み合わせに対してオイラーの定理が成り立つこと確認するプログラムを書きなさい。(aのφ(n)乗を計算するとint型で扱える範囲を超えてしまうので、aのi乗をnで割った余りを順次求めることでこの問題を避けられる。)
出力の形式は定理が成り立っていれば、
n = ①, a = ②: verified
成り立っていなければ
***n = ①, a = ②: counterexample found!***
としなさい。
調べる順番はnの小さい順、同じnに対してaの小さい順としなさい。出力の出だしは
n = 2, a = 1: verified
n = 3, a = 1: verified
n = 3, a = 2: verified
n = 4, a = 1: verified
n = 4, a = 3: verified
n = 5, a = 1: verified
n = 5, a = 2: verified
n = 5, a = 3: verified
n = 5, a = 4: verified
n = 6, a = 1: verified
となる。

if文,ループ,配列までしか習っていないので,できる限りその知識内で書いて欲しいです🙇🏻‍♀️

かずま

Re: オイラーの定理

#2

投稿記事 by かずま » 5年前

問題の丸投げは、フォーラムルールに反します。
ヒントを差し上げますので、それを使ってコードを書いてください。

1.「a と b が互いに素である」は、
 「a と b の最小公倍数が 1 である」と同じです。

2.「aφ(n) - 1 が n で割り切れる」は、
 「aφ(n) を n で割った余りが 1」と同じです。

3.「a * a * a % n」は、
 「1 * a % n * a % n * a % n」と同じです。

コード:

int gcd(int a, int b)
{
	int r;
	while (r = a % b) a = b, b = r;
	return b;
}

int phi(int n)
{
	int k = 0;
	for (int i = 1; i < n; i++)
		if (gcd(n, i) == 1) k++;
	return k;
}

int pow_mod(int a, int k, int n)  // pow(a, k) % n
{
	int p = 1;
	while (k-- > 0) p = p * a % n;
	return p;
}

かずま

Re: オイラーの定理

#3

投稿記事 by かずま » 5年前

かずま さんが書きました:
5年前
1.「a と b が互いに素である」は、
 「a と b の最小公倍数が 1 である」と同じです。
すみません。訂正です。
1.「a と b が互いに素である」は、
 「a と b の最大公約数が 1 である」と同じです。

main を書いて実行してみると、127行でした。

コード:

n = 2, a = 1: verified
n = 3, a = 1: verified
n = 3, a = 2: verified
n = 4, a = 1: verified
n = 4, a = 3: verified
n = 5, a = 1: verified
n = 5, a = 2: verified
n = 5, a = 3: verified
n = 5, a = 4: verified
n = 6, a = 1: verified
  ...
n = 19, a = 17: verified
n = 19, a = 18: verified
n = 20, a = 1: verified
n = 20, a = 3: verified
n = 20, a = 7: verified
n = 20, a = 9: verified
n = 20, a = 11: verified
n = 20, a = 13: verified
n = 20, a = 17: verified
n = 20, a = 19: verified
counterexample found! はありません。

かずま

Re: オイラーの定理

#4

投稿記事 by かずま » 5年前

かずま さんが書きました:
5年前
main を書いて実行してみると、127行でした。
またまた、訂正です。
n は、20 までではなく、50までですね。
結果は、127行ではなく、773行でした。

コード:

n = 2, a = 1: verified
n = 3, a = 1: verified
n = 3, a = 2: verified
n = 4, a = 1: verified
n = 4, a = 3: verified
n = 5, a = 1: verified
n = 5, a = 2: verified
n = 5, a = 3: verified
n = 5, a = 4: verified
n = 6, a = 1: verified
  ...
n = 50, a = 27: verified
n = 50, a = 29: verified
n = 50, a = 31: verified
n = 50, a = 33: verified
n = 50, a = 37: verified
n = 50, a = 39: verified
n = 50, a = 41: verified
n = 50, a = 43: verified
n = 50, a = 47: verified
n = 50, a = 49: verified
counterexample found! はありません。

nana0627

Re: オイラーの定理

#5

投稿記事 by nana0627 » 5年前

文字が多くて見づらくてごめんなさい。
ヒントを見て頑張ってみましたが、aが全て1になってしまいました。

コード:

#include <stdio.h>
#define NUMBER 50
int main (void){
  int a,b,c,d,e,f,g,h,i,count;
  int n[NUMBER];
  for (a = 2; a <= NUMBER; a++){
    count = 0;
    f = 0;
    for (b = 1; b < a; b++){
      c = a;
      d = b;
      while (c % d != 0){
	e = c % d;
	c = d;
	d = e;
      }
      if (d == 1){
	count++;
	f++;
	n[f] = b;
      }
      i = count;
      for (g = 1; g <= i; g++){
	h = 1;
	while (count > 0){
	  h = h * n[g] % a;
	  count--;
	}
	if (h == 1) 
	  printf("n = %d, a = %d: verified\n",a,n[g]);
	else
	  printf("***n = %d, a = %d: counterexample found!\n",a,n[g]);
      }
    }
  }
  return (0);
}

かずま

Re: オイラーの定理

#6

投稿記事 by かずま » 5年前

nana0627 さんが書きました:
5年前
文字が多くて見づらくてごめんなさい。
インデントを スペース 2個、4個、6個、タブ 1個で書いていますね。
この掲示板で codeタグを使うと、タブはスペース 4個に
置き換えられて見にくくなります。

変数の n と a が問題文と逆なのも分かりにくい原因のひとつです。
また、サブ関数を使わず、main に全部入れていることも問題です。
nana0627 さんが書きました:
5年前
ヒントを見て頑張ってみましたが、aが全て1になってしまいました。
aφ(n) の計算は、φ(n) が求まった後でないとできません。
そのプログラムは、φ(n) を求める途中の値 countを使って
acount を計算しているのでダメです。

さて最低限の修正は、

コード:

#include <stdio.h>
#define NUMBER 50
int main (void){
  int a,b,c,d,e,f,g,h,i,count;
  int n[NUMBER];
  for (a = 2; a <= NUMBER; a++){
    count = 0;
    f = 0;
    for (b = 1; b < a; b++){
      c = a;
      d = b;
      while (c % d != 0){
        e = c % d;
        c = d;
        d = e;
      }
      if (d == 1){
        count++;
        f++;
        n[f] = b;
      }
    }  // ★追加
    {  // ★追加
      i = count;
      for (g = 1; g <= i; g++){
        h = 1;
        count = i;  // ★追加
        while (count > 0){
          h = h * n[g] % a;
          count--;
        }
        if (h == 1) 
          printf("n = %d, a = %d: verified\n",a,n[g]);
        else
          printf("***n = %d, a = %d: counterexample found!\n",a,n[g]);
      }
    }
  }
  return (0);
}
サブ関数を使えば、

コード:

#include <stdio.h>

#define NUM 50

int gcd(int a, int b)
{
	int r;
	while (r = a % b) a = b, b = r;
	return b;
}

int phi(int n, int *a)
{
	int k = 0;
	for (int i = 1; i < n; i++)
		if (gcd(n, i) == 1) a[k++] = i;
	return k;
}

int pow_mod(int a, int k, int n)  // pow(a, k) % n
{
	int p = 1;
	while (k-- > 0) p = p * a % n;
	return p;
}

int main(void)
{
	for (int a[NUM], n = 2; n <= NUM; n++)
		for (int k = phi(n, a), i = 0; i < k; i++)
			printf(pow_mod(a[i], k, n) == 1 ? "n = %d, a = %d: verified\n"
				: "***n = %d, a = %d: counterexample found!***\n", n, a[i]);
}

かずま

Re: オイラーの定理

#7

投稿記事 by かずま » 5年前

main だけで書けば、短くはなりますが、コメントが必要でしょう。

コード:

#include <stdio.h>

#define NUM 50

int main(void)
{
	int a[NUM], n, m, i, j, k, r;
	for (n = 2; n <= NUM; n++) {
		for (k = 0, m = 1; m < n; m++) {     // m は a の候補
			for (i = n, j = m; r = i % j; j = r) i = j;    // j = gcd(n, m)
			if (j == 1) a[k++] = m;    // k = φ(n), 互いに素である a の個数
		}
		for (i = 0; i < k; i++) {            // すべての a[i] について調べる
			for (m = 1, j = k; j--; ) m = m * a[i] % n; // m = pow(a, k) % n
			if (m == 1)
				printf("n = %d, a = %d: verified\n", n, a[i]);
			else
				printf("***n = %d, a = %d: kerexample found!***\n", n, a[i]);
		}
	}
}

返信

“C言語何でも質問掲示板” へ戻る