모듈러 곱셈 역함수를 찾으십시오.

Question

다음 해결책을 찾을 수 있습니다 : 9^(- 1) % M 즉 9 모듈로 M의 역함수 2 < = M < = 10^9 소수 일 수없고 gcd 9, M)은 그러한 해를 찾을 수 없다면 1이되지 않을 수도있다. ((10^n-1)/9) % M 1 < = n < = 10^16

Answer 1

,

PowerMod[9,-1,m] 

이 당신에게 9의 역, 모듈로 m을 줄 것이다 : 이것은 어떤 경우에는이 작업을 수행하는 내장 함수가, 텅스텐 - 티카 난 당신이 매스 매 티카의 맥락에서 요구하는 가정 태그가 ~를 위해 네가 원하는 너의 가치.

Table[PowerMod[9,-1,m],{m,2,1000}] 

가 생성됩니다 : 당신이 그 목록에서 잘못된 출력을 제거 할 수

PowerMod::ninv: 0 is not invertible modulo 3. >> 
PowerMod::ninv: 3 is not invertible modulo 6. >> 
PowerMod::ninv: 0 is not invertible modulo 9. >> 
General::stop: Further output of PowerMod::ninv will be 
    suppressed during this calculation. >> 
{1, PowerMod[9, -1, 3], 1, 4, PowerMod[9, -1, 6], 4, 1, 
PowerMod[9, -1, 9], 9, 5, PowerMod[9, -1, 12], 3, 11, 
PowerMod[9, -1, 15], 9, 2, PowerMod[9, -1, 18], 17, 9, 
PowerMod[9, -1, 21], 5, 18, PowerMod[9, -1, 24], 14, 3, 
PowerMod[9, -1, 27], 25, 13, PowerMod[9, -1, 30], 7, 25, 
PowerMod[9, -1, 33], 19, 4, PowerMod[9, -1, 36], 33, 17, 
PowerMod[9, -1, 39], 9, 32, PowerMod[9, -1, 42], 24, 5, 
PowerMod[9, -1, 45], 41, 21, PowerMod[9, -1, 48], 11, 39, 
PowerMod[9, -1, 51], 29, 6, PowerMod[9, -1, 54], 49, 25, 
PowerMod[9, -1, 57], 13, 46, PowerMod[9, -1, 60], 34, 7, 
PowerMod[9, -1, 63], 57, 29, PowerMod[9, -1, 66], 15, 53, 
PowerMod[9, -1, 69], 39, 8, PowerMod[9, -1, 72], 65, 33, 
PowerMod[9, -1, 75], 17, 60, PowerMod[9, -1, 78], 44, 9, 
PowerMod[9, -1, 81], 73, 37, PowerMod[9, -1, 84], 19, 67, 
PowerMod[9, -1, 87], 49, 10, PowerMod[9, -1, 90], 81, 41, 
PowerMod[9, -1, 93], 21, 74, PowerMod[9, -1, 96], 54, 11, 
PowerMod[9, -1, 99], 89} 

는 :

Select[%, IntegerQ] 

주는 :

{1, 1, 4, 4, 1, 9, 5, 3, 11, 9, 2, 17, 9, 5, 18, 14, 3, 25, 13, 7, 
25, 19, 4, 33, 17, 9, 32, 24, 5, 41, 21, 11, 39, 29, 6, 49, 25, 13, 
46, 34, 7, 57, 29, 15, 53, 39, 8, 65, 33, 17, 60, 44, 9, 73, 37, 19, 
67, 49, 10, 81, 41, 21, 74, 54, 11, 89} 

당신이 원하는 경우 현명한 생각을하기 위해, 당신은 또한 이것을 조직 할 수 있습니다. 이 사용하는 고급 티카 구문을 달성하기 위해 9 가지 방법으로 서로 소되지 않은 요소를 생략하여 더 나은 테이블은 다음과 같습니다

{{2, 1}, {4, 1}, {5, 4}, {7, 4}, {8, 1}, {10, 9}, {11, 5}, {13, 3}, 
{14, 11}, {16, 9}, {17, 2}, {19, 17}, {20, 9}, {22, 5}, {23, 18}, 
{25, 14}, {26, 3}, {28, 25}, {29, 13}, {31, 7}, {32, 25}, {34, 19}, 
{35, 4}, {37, 33}, {38, 17}, {40, 9}, {41, 32}, {43, 24}, {44, 5}, 
{46, 41}, {47, 21}, {49, 11}, {50, 39}, {52, 29}, {53, 6}, {55, 49}, 
{56, 25}, {58, 13}, {59, 46}, {61, 34}, {62, 7}, {64, 57}, {65, 29}, 
{67, 15}, {68, 53}, {70, 39}, {71, 8}, {73, 65}, {74, 33}, {76, 17}, 
{77, 60}, {79, 44}, {80, 9}, {82, 73}, {83, 37}, {85, 19}, {86, 67}, 
{88, 49}, {89, 10}, {91, 81}, {92, 41}, {94, 21}, {95, 74}, {97, 54}, 
{98, 11}, {100, 89}} 

당신에게 목록을 제공 : 당신 출력을 제공하는

Map[{#, PowerMod[9, -1, m]} &, Select[Range[100], GCD[#, 9] == 1 &]] 

각각의 쌍은 m 값을 가지며, 그 역수는 m 값을 모듈로한다. 예를 들어, {61,34}가 해당 목록에 있습니다. 즉, 9 * 34는 1 mod 61입니다. this is right을 확인할 수 있습니다.