こんにちは。
タイトルの通りの質問なのですが、過去ログを参考にしても特別分からないところがあったため、質問させて下さい。
11^-1 ≡ x(mod 31)
このxを求めたいのですが、11x * 31y = gcd(11, 31)として解いたら、
-14 * 11 + 5 * 31 = 1
となってしまい、うまくいきません。
以下、自分なりの解法です。
-----------------------------------------------------
11^-1 ≡ x(mod 31)より、11x ≡ 1(mod31)
これは、11x + 31y = 1を示す。
gcd(11, 31) 11 = a, 31 = b とする
= gcd(31, 11) → b = 2a + 9 → 9 = -2a + b
= gcd(11, 9) → a = (-2a + b) + 2 → 2 = 3a - b
= gcd(9, 2) → -2a + b = 4(3a - b) + 1 ―(1)
= gcd(2, 1)
= gcd(1, 0) = 1
(1)の式より、-14a + 5b = 1
先ほどの式と照らし合わせて、(x, y) = (-14, 5)
したがって、11^-1 ≡ -14(mod 31)
-----------------------------------------------------
おそらく、11x > 31yの条件が取り入れられてないのが原因だと思いますが、どう使えばいいかわからないです。
どなたか正しい解法を教えてください。
よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- 数学 g=gcd(a,b)とする。このときa|cかつb|cならばab|cgを示せ。という問題を c=qa, 3 2023/05/21 18:31
- 数学 一次合同式と連立合同式の問題について 3 2022/05/07 15:47
- 数学 大学数学 「条件:t進表現において、何乗しても右から2桁が変わらない2桁の自然数が存在する。」 上記 7 2023/06/28 22:25
- 数学 m, n を整数. g.c.d(m, n) = d, l.c.m(m, n) = l とすると { 2 2022/05/22 18:54
- 数学 乗法公式の問題についてです。 (x-y)(2x+y)??? 2 2022/10/18 19:50
- Excel(エクセル) エクセルの数式で教えてください。 2 2023/04/13 10:55
- 数学 p を奇素数 ((b) は p≠5) とするとき, 以下の同値関係を示せ. (a) (-2/p) = 3 2022/07/03 16:35
- Excel(エクセル) 下記エクセルの式がなぜこうなるのか理由が知りたいです。 6 2022/08/20 00:43
このQ&Aを見た人はこんなQ&Aも見ています
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
完全数はどうして「完全」と名...
-
直角三角形じゃないのに三平方...
-
円周角の定理を使う問題につい...
-
至上最難問の数学がとけた
-
行列のn乗について
-
数A nは自然数とする。n , n+2 ...
-
数IIIの定理、受験で使っていい...
-
合同方程式13x≡7(mod84)の答え...
-
大学の記述入試で外積は使えま...
-
十分性の確認について
-
「整数係数方程式の有理解の定...
-
合同式の性質についてです。 な...
-
非正規形の微分方程式
-
lim[x→+∞](x^n/e^x)=0 の証明
-
三角形の3辺の長さの性質の証明
-
x^100を(x+1)^2で割ったときの...
-
ディリクレ指標について( mod=5...
-
モーレの定理
-
3以上9999以下の奇数aで、(a^2)...
-
複素関数と実関数のテーラー展...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
過去に 「ii) f(z)=1/(z^2-1) r...
-
【遊びのピタゴラスイッチはな...
-
直角三角形じゃないのに三平方...
-
大学の記述入試で外積は使えま...
-
lim[x→+∞](x^n/e^x)=0 の証明
-
定理と法則の違い
-
至上最難問の数学がとけた
-
実数の整列化について
-
十分性の確認について
-
AとBはn次正方行列とする。 積A...
-
ほうべき(方巾)の定理について
-
ファルコンの定理は解かれまし...
-
パップスギュルダンの定理について
-
オイラーの多面体定理の拡張
-
微分形式,微分幾何学の参考書
-
ディリクレ指標について( mod=5...
-
x^100を(x+1)^2で割ったときの...
-
nを整数とする。このとき、n^2...
-
大学数学 解答
-
4.6.8で割るとあまりはそれぞれ...
おすすめ情報