n is a number and n=(p1^c) * (p2^d).Here p1 and p2 are prime. Let a=p1^c and b=p2^d.
gcd(i,n)=
gcd(i,a) *
gcd(i,b)
How can to prove this? Any explanation? Thanks in advance.
# | User | Rating |
---|---|---|
1 | tourist | 3845 |
2 | jiangly | 3707 |
3 | Benq | 3630 |
4 | orzdevinwang | 3573 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3532 |
8 | ecnerwala | 3501 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | adamant | 163 |
3 | awoo | 162 |
4 | nor | 153 |
5 | maroonrk | 152 |
6 | -is-this-fft- | 151 |
7 | TheScrasse | 150 |
8 | Petr | 145 |
9 | atcoder_official | 144 |
9 | pajenegod | 144 |
Math,Gcd
n is a number and n=(p1^c) * (p2^d).Here p1 and p2 are prime. Let a=p1^c and b=p2^d.
gcd(i,n)=
gcd(i,a) *
gcd(i,b)
How can to prove this? Any explanation? Thanks in advance.
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
en5 |
![]() |
sahasumit288 | 2016-10-15 22:33:31 | 3 | Tiny change: 'b)\n\nHow can to prove ' -> 'b)\n\nHow to prove ' | |
en4 |
![]() |
sahasumit288 | 2016-10-15 22:29:28 | 2 | Tiny change: 'gcd(i,b)\nHow can ' -> 'gcd(i,b)\n\nHow can ' | |
en3 |
![]() |
sahasumit288 | 2016-10-15 22:28:23 | 79 | ||
en2 |
![]() |
sahasumit288 | 2016-10-15 22:26:07 | 3 | ||
en1 |
![]() |
sahasumit288 | 2016-10-15 22:25:19 | 216 | Initial revision (published) |
Name |
---|