mersenneforum.org Phi mod 11 is congruent 4 and 8
 Register FAQ Search Today's Posts Mark Forums Read

 2022-06-21, 03:34 #1 x13420x   Jun 2022 2×5 Posts Phi mod 11 is congruent 4 and 8 What about other irrational numbers. e seens to be 6.....what about pi.....Would the square root of 2 be an imaginary number?
2022-06-21, 11:39   #2
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts

Quote:
 Originally Posted by x13420x What about other irrational numbers. e seens to be 6.....what about pi.....Would the square root of 2 be an imaginary number?
Phi = (1+sqrt(5))/2, and sqrt(5) mod 11 = 4 or 7 (5 has two square roots mod 11: 4 and 7, since 4^2 == 5 mod 11, 7^2 == 5 mod 11), thus Phi == (1+4)/2 == 5/2 == 8 (mod 11) or Phi == (1+7)/2 == 8/2 == 4 mod 11

Phi (mod n) only exist when 5 is quadratic residue mod n (since Phi has sqrt(5)) and n is coprime to 2 (since Phi has 1/2)

Code:
n     Phi (mod n)
1     0
5     3
11    4 or 8
19    5 or 14
29    6 or 23
31    12 or 19
41    7 or 34
55    8 or 48
59    25 or 34
61    17 or 44
71    9 or 62
79    29 or 50
89    10 or 79
95    33 or 43
101   23 or 78
109   11 or 98
121   37 or 85
131   12 or 119
139   63 or 76
145   23 or 93
149   40 or 109
151   28 or 123
155   43 or 143
179   74 or 105
181   14 or 169

Last fiddled with by sweety439 on 2022-06-21 at 11:49

2022-06-21, 11:42   #3
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72·73 Posts

Quote:
 Originally Posted by x13420x What about other irrational numbers. e seens to be 6.....what about pi.....Would the square root of 2 be an imaginary number?
e and pi are transcendental numbers .... they cannot be calculated mod n, unless you use 355/113 instead of pi ....

the square root of 2 is imaginary number if and only if 2 is not quadratic residue to your modulo, e.g. sqrt(2) mod 3, in Z3, you will find a field extension, i.e. Z3(sqrt(2))

2022-06-21, 18:58   #4
Dr Sardonicus

Feb 2017
Nowhere

61×97 Posts

Quote:
 Originally Posted by sweety439 Phi = (1+sqrt(5))/2, and sqrt(5) mod 11 = 4 or 7 (5 has two square roots mod 11: 4 and 7, since 4^2 == 5 mod 11, 7^2 == 5 mod 11), thus Phi == (1+4)/2 == 5/2 == 8 (mod 11) or Phi == (1+7)/2 == 8/2 == 4 mod 11 Phi (mod n) only exist when 5 is quadratic residue mod n (since Phi has sqrt(5)) and n is coprime to 2 (since Phi has 1/2) Code: n Phi (mod n) 1 0 5 3 11 4 or 8 19 5 or 14 29 6 or 23 31 12 or 19 41 7 or 34 55 8 or 48 59 25 or 34 61 17 or 44 71 9 or 62 79 29 or 50 89 10 or 79 95 33 or 43 101 23 or 78 109 11 or 98 121 37 or 85 131 12 or 119 139 63 or 76 145 23 or 93 149 40 or 109 151 28 or 123 155 43 or 143 179 74 or 105 181 14 or 169
I believe the interpretation is correct. The key is that there is a defining polynomial. The required residues are the zeroes of x^2 - x - 1 (mod n). If n =p, a prime number, and p is congruent to 1 or 4 (mod 5), there are two distinct roots of

x^2 - x - 1 == 0 (mod p)

If p = 5 there is one repeated root. For p == 2 or 3 (mod 5) there are no roots.

However, at least for the prime moduli other than 5 and 11, one of the residues in the quoted portion above appears to be off by 1.
Code:
? forprime(p=2,200,r=p%5;if(r==1||r==4,M=factormod(x^2-x-1,p);v=subst(M[,1],x,0)~;print(p" "lift(-v))))
11 [8, 4]
19 [15, 5]
29 [24, 6]
31 [19, 13]
41 [35, 7]
59 [34, 26]
61 [44, 18]
71 [63, 9]
79 [50, 30]
89 [80, 10]
101 [79, 23]
109 [99, 11]
131 [120, 12]
139 [76, 64]
149 [109, 41]
151 [124, 28]
179 [105, 75]
181 [168, 14]
191 [103, 89]
199 [138, 62]

Last fiddled with by Dr Sardonicus on 2022-06-21 at 19:17

2022-06-22, 03:04   #5
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts

Quote:
 Originally Posted by Dr Sardonicus I believe the interpretation is correct. The key is that there is a defining polynomial. The required residues are the zeroes of x^2 - x - 1 (mod n). If n =p, a prime number, and p is congruent to 1 or 4 (mod 5), there are two distinct roots of x^2 - x - 1 == 0 (mod p) If p = 5 there is one repeated root. For p == 2 or 3 (mod 5) there are no roots. However, at least for the prime moduli other than 5 and 11, one of the residues in the quoted portion above appears to be off by 1. Code: ? forprime(p=2,200,r=p%5;if(r==1||r==4,M=factormod(x^2-x-1,p);v=subst(M[,1],x,0)~;print(p" "lift(-v)))) 11 [8, 4] 19 [15, 5] 29 [24, 6] 31 [19, 13] 41 [35, 7] 59 [34, 26] 61 [44, 18] 71 [63, 9] 79 [50, 30] 89 [80, 10] 101 [79, 23] 109 [99, 11] 131 [120, 12] 139 [76, 64] 149 [109, 41] 151 [124, 28] 179 [105, 75] 181 [168, 14] 191 [103, 89] 199 [138, 62]
I have corrected my program and searched the residues up to mod 1000:

Code:
1: 0,
5: 3,
11: 4, 8,
19: 5, 15,
29: 6, 24,
31: 13, 19,
41: 7, 35,
55: 8, 48,
59: 26, 34,
61: 18, 44,
71: 9, 63,
79: 30, 50,
89: 10, 80,
95: 43, 53,
101: 23, 79,
109: 11, 99,
121: 37, 85,
131: 12, 120,
139: 64, 76,
145: 53, 93,
149: 41, 109,
151: 28, 124,
155: 13, 143,
179: 75, 105,
181: 14, 168,
191: 89, 103,
199: 62, 138,
205: 48, 158,
209: 15, 81, 129, 195,
211: 33, 179,
229: 82, 148,
239: 16, 224,
241: 52, 190,
251: 118, 134,
269: 72, 198,
271: 17, 255,
281: 38, 244,
295: 93, 203,
305: 18, 288,
311: 59, 253,
319: 140, 151, 169, 180,
331: 117, 215,
341: 19, 81, 261, 323,
349: 144, 206,
355: 63, 293,
359: 106, 254,
361: 43, 319,
379: 20, 360,
389: 152, 238,
395: 188, 208,
401: 112, 290,
409: 130, 280,
419: 21, 399,
421: 111, 311,
431: 91, 341,
439: 70, 370,
445: 188, 258,
449: 166, 284,
451: 48, 158, 294, 404,
461: 22, 440,
479: 229, 251,
491: 74, 418,
499: 225, 275,
505: 23, 483,
509: 122, 388,
521: 100, 422,
541: 173, 369,
545: 208, 338,
551: 24, 53, 499, 528,
569: 233, 337,
571: 274, 298,
589: 81, 205, 385, 509,
599: 25, 575,
601: 137, 465,
605: 158, 448,
619: 243, 377,
631: 110, 522,
641: 279, 363,
649: 26, 85, 565, 624,
655: 143, 513,
659: 201, 459,
661: 58, 604,
671: 140, 323, 349, 532,
691: 222, 470,
695: 203, 493,
701: 27, 675,
709: 171, 539,
719: 330, 390,
739: 119, 621,
745: 258, 488,
751: 211, 541,
755: 28, 728,
761: 92, 670,
769: 339, 431,
779: 281, 376, 404, 499,
781: 63, 151, 631, 719,
809: 343, 467,
811: 29, 783,
821: 213, 609,
829: 96, 734,
839: 342, 498,
841: 227, 615,
859: 277, 583,
869: 30, 129, 741, 840,
881: 327, 555,
895: 433, 463,
899: 267, 354, 546, 633,
905: 168, 738,
911: 68, 844,
919: 317, 603,
929: 31, 899,
941: 228, 714,
955: 103, 853,
961: 199, 763,
971: 174, 798,
979: 169, 455, 525, 811,
991: 32, 960,
995: 138, 858,

2022-06-23, 15:59   #6
x13420x

Jun 2022

2×5 Posts

Quote:
 Originally Posted by sweety439 e and pi are transcendental numbers .... they cannot be calculated mod n, unless you use 355/113 instead of pi .... the square root of 2 is imaginary number if and only if 2 is not quadratic residue to your modulo, e.g. sqrt(2) mod 3, in Z3, you will find a field extension, i.e. Z3(sqrt(2))
Thanks for your explanation are there any interesting transedental numbers that can be taken mod 11.....so instead of 1/n! to calculate e we could do 11/n! which would be congruent 11 but thats kind of boring.....and if you put another factorial type object in the numerator you would get a quadratic.....I believe.....

 2022-06-24, 05:40 #7 x13420x   Jun 2022 2·5 Posts so I guess it would need to be N^11/N!.....to avoid division by 11.....
 2022-06-24, 05:57 #8 paulunderwood     Sep 2002 Database er0rr 25×7×19 Posts I think you meant 11^N/(N!).
2022-06-24, 05:57   #9
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts

Quote:
 Originally Posted by x13420x Thanks for your explanation are there any interesting transedental numbers that can be taken mod 11.....so instead of 1/n! to calculate e we could do 11/n! which would be congruent 11 but thats kind of boring.....and if you put another factorial type object in the numerator you would get a quadratic.....I believe.....
You want to use the series 1/0! + 1/1! + 1/2! + ... to calculated mod 11, but from 1/11!, the denominator is divisible by 11 and you will divide by zero.

2022-06-24, 12:28   #10
x13420x

Jun 2022

2×5 Posts

Quote:
 Originally Posted by paulunderwood I think you meant 11^N/(N!).
Yes thank you

11^0/0! + 11^1/1! + 11^2/2!....... I believe this is transendental but now that I think about it I think it will go to infinity......I am doubting that this converges on a number....sorry seems I am babbling now....

Last fiddled with by x13420x on 2022-06-24 at 12:30

 2022-06-24, 12:36 #11 x13420x   Jun 2022 10102 Posts Did you guys notice when you add the 2 results you get the modulo number plus 1? like 8 + 4 = 11 + 1

 Similar Threads Thread Thread Starter Forum Replies Last Post enzocreti enzocreti 1 2020-03-03 06:12 enzocreti enzocreti 1 2020-02-14 16:56 enzocreti enzocreti 2 2020-02-12 15:14 enzocreti enzocreti 0 2020-01-09 11:56 smslca Math 2 2012-01-29 11:30

All times are UTC. The time now is 00:19.

Sat Aug 20 00:19:37 UTC 2022 up 1 day, 21:48, 1 user, load averages: 1.77, 1.46, 1.36

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔