かなり難しい問題です

質問

素数でないNと１～N-1の間の数Aを考え、AとNが互いに素だが、A＾（N-1）－１がNで割り切れるNとAの組み合わせを最低ひとつ見つける。というものなのですが、どなたか分かりますでしょうか？
ちなみに＾の後ろの括弧内はAの乗数です。
問題の意味が分からないなど、指摘していただければと思います。

回答No.4

nag0720 · ベストアンサー

N-1 = 2^p

と限定すると x^2-1=(x-1)(x+1) の公式を利用して、

A^(N-1)-1 = A^(2^p)-1 = (A-1)*(A+1)*(A^2+1)*…*(A^(2^(p-1))+1)

N=A+1 とすると A^(N-1)-1 は N で割り切れます。

あとは、N が素数とならない p を求めればＯＫ

p=3 のとき、2^3=8 から

N=9 , A=8

p=6 のとき、2^6=64 から

N=65 , A=64

p=7 のとき、2^7=128 から

N=129 , A=128

また、N=A^2+1 の場合も A^(N-1)-1 は N で割り切れます。

p=6　のとき　8^2+1 = 65 　であることから

N=65 , A=8

も答えです。

回答No.3

rabbit_cat

そういうＮを「フェルマー擬素数」といいます。
フェルマーテストを通ってしまう合成数のことです。
http://mitv2.net/python/prime2.html
の、「3 擬素数」ってところに、一例が載っています。
「フェルマーの小定理」「フェルマーテスト」「擬素数」とかで検索すると問題の背景がわかると思います。
最近似たような質問がありました。
http://oshiete1.goo.ne.jp/qa4996054.html

回答No.2

bgm38489

A^(N-1)-1=N*B（Bは自然数）として、
A^(N-1)=N*B+1としてみたら、答えは見えてきたけど。求めよ、というのではなくて、見つけよですね？
3の倍数以外の平方数は、3の倍数+1となる性質を利用。

回答No.1

kaz-a

N=9,A=8
総当りテストの二回目に確認する組み合わせですが...

お礼

確かに成り立つことを確認できました。
ありがとうございました！
総当りテスト？という便利なものもあるのですね！