Phi mod 11 is congruent 4 and 8

[x13420x]

What about other irrational numbers. e seens to be 6.....what about pi.....Would the square root of 2 be an imaginary number?

[sweety439]

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)

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

[sweety439]

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))

[Dr Sardonicus]

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)

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.

? 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]

[sweety439]

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.

? 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:

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,

[x13420x]

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.....

[x13420x]

so I guess it would need to be N^11/N!.....to avoid division by 11.....

[paulunderwood]

I think you meant 11^N/(N!).

[sweety439]

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.

[x13420x]

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....

[x13420x]

Did you guys notice when you add the 2 results you get the modulo number plus 1? like 8 + 4 = 11 + 1