Remainder of the product of the relatively prime numbers

  • Thread starter whodsow
  • Start date
  • #1
12
0

Main Question or Discussion Point

Hi all, I had a problem, pls help me.

Let [tex]b_1 < b_2 < \cdots < b_{\varphi(m)}[/tex] be the integers between 1 and m that are relatively prime to m (including 1), of course, [tex]\varphi(m)[/tex] is the number of integers between 1 and m that are relatively prime to m, and let [tex]B = b_1b_2b_3{\cdots}b_{\varphi(m)}[/tex] be their product.
Please find a pattern for when [tex]B\equiv1 ({\bmod}\ m)[/tex] and when [tex]B\equiv-1 ({\bmod}\ m)[/tex].

Thanks and Regards.
 
Last edited:

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Code:
ff(m)=centerlift(prod(b=2,m,if(gcd(m,b)==1,b,1),Mod(1,m)))
for(m=2,20,print(m" "ff(m)))
in Pari/gp gives
Code:
2 1
3 -1
4 -1
5 -1
6 -1
7 -1
8 1
9 -1
10 -1
11 -1
12 1
13 -1
14 -1
15 1
16 1
17 -1
18 -1
19 -1
20 1
Does that help?
 
  • #3
12
0
Thank you, I've gotten the similar table.
Code:
m	phi	rem
1	1	1
4	2	-1
6	2	-1
8	4	1
9	6	-1
10	4	-1
12	4	1
14	6	-1
15	8	1
16	8	1
18	6	-1
20	8	1
21	12	1
22	10	-1
24	8	1
25	20	-1
26	12	-1
27	18	-1
28	12	1
30	8	1
32	16	1
33	20	1
34	16	-1
35	24	1
36	12	1
38	18	-1
39	24	1
40	16	1
42	12	1
44	20	1
45	24	1
46	22	-1
48	16	1
49	42	-1
50	20	-1
51	32	1
52	24	1
54	18	-1
55	40	1
56	24	1
57	36	1
58	28	-1
60	16	1
62	30	-1
63	36	1
64	32	1
65	48	1
66	20	1
68	32	1
69	44	1
70	24	1
72	24	1
74	36	-1
75	40	1
76	36	1
77	60	1
78	24	1
80	32	1
81	54	-1
82	40	-1
84	24	1
85	64	1
86	42	-1
87	56	1
88	40	1
90	24	1
91	72	1
92	44	1
93	60	1
94	46	-1
95	72	1
96	32	1
98	42	-1
99	60	1
but I still can't find the ppattern, and I have only found that if 4 does not divide [tex]\phi(m)[/tex] then [tex]B{\equiv}-1[/tex], and if [tex]B{\equiv}1[/tex], there must be that 4 divides [tex]\phi(m)[/tex]
 
Last edited:

Related Threads for: Remainder of the product of the relatively prime numbers

Replies
6
Views
3K
Replies
2
Views
3K
  • Last Post
Replies
2
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
6
Views
5K
Top