「互いに素である正の整数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: オイラーの定理
問題の丸投げは、フォーラムルールに反します。
ヒントを差し上げますので、それを使ってコードを書いてください。
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」と同じです。
ヒントを差し上げますので、それを使ってコードを書いてください。
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」と同じです。
Re: オイラーの定理
すみません。訂正です。
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
Re: オイラーの定理
またまた、訂正です。かずま さんが書きました: ↑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
Re: オイラーの定理
文字が多くて見づらくてごめんなさい。
ヒントを見て頑張ってみましたが、aが全て1になってしまいました。
ヒントを見て頑張ってみましたが、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: オイラーの定理
インデントを スペース 2個、4個、6個、タブ 1個で書いていますね。nana0627 さんが書きました: ↑5年前文字が多くて見づらくてごめんなさい。
この掲示板で codeタグを使うと、タブはスペース 4個に
置き換えられて見にくくなります。
変数の n と a が問題文と逆なのも分かりにくい原因のひとつです。
また、サブ関数を使わず、main に全部入れていることも問題です。
aφ(n) の計算は、φ(n) が求まった後でないとできません。nana0627 さんが書きました: ↑5年前ヒントを見て頑張ってみましたが、aが全て1になってしまいました。
そのプログラムは、φ(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: オイラーの定理
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]);
}
}
}