新未名空间

任意正整数有唯一分解n = p1^k1 * p2^k2 * ... * pm^km， pi为不同的质数

请证明或者证伪当n > 2的时候, 记从1到n-1中，与n互质的正整数的个数为a，那么

2^m | a

（ヅ） 写了： 2023年 12月 10日 18:24 任意正整数有唯一分解n = p1^k1 * p2^k2 * ... * pm^km， pi为不同的质数

请证明或者证伪当n > 2的时候, 记从1到n-1中，与n互质的正整数的个数为a，那么

2^m | a

Do you want 2^{m-1}|a?

成立的。此式对质数成立。 而a是Euler totient function,有乘性，所以都成立。

rgg 写了： 2023年 12月 10日 23:06 成立的。此式对质数成立。 而a是Euler totient function,有乘性，所以都成立。

True, with only the exception of the case p=2. For example, 6=2*3, so m=2, but \phi(6)=2 not divisible by 2^2.

changbaihou 写了： 2023年 12月 11日 12:00 True, with only the exception of the case p=2. For example, 6=2*3, so m=2, but \phi(6)=2 not divisible by 2^2.

确实。10=2*5都可以，为什么6=2*3会出问题呢？

TheMatrix 写了： 2023年 12月 11日 12:59 确实。10=2*5都可以，为什么6=2*3会出问题呢？

因为5-1=4等于2^2

totient function \phi(n) = p1^{k1-1} * p2^{k2-1} * ... * pm^{km-1} * (p1-1) * (p2 - 1) * ... * (pm - 1)

分成3部分, p1^{k1-1} * p2^{k2-1} * ... * pm^{km-1} 为整数; p1 如果等于2，那么p1 - 1 = 1;后面的 (p2 - 1) * ... * (pm - 1)每一项都是偶数


多出来一个2 canceling out 1/2

（ヅ） 写了： 2023年 12月 10日 18:24 任意正整数有唯一分解n = p1^k1 * p2^k2 * ... * pm^km， pi为不同的质数

请证明或者证伪当n > 2的时候, 记从1到n-1中，与n互质的正整数的个数为a，那么

2^m | a

2^m | a 是啥？

Pegasi 写了： 2023年 12月 11日 13:54 2^m | a 是啥？

整除

编辑器可以写上下标，帮你重写了

（ヅ） 写了： 2023年 12月 10日 18:24 任意正整数有唯一分解n = p₁^k₁ p₂^k₂ ... p_m^k_m， p_i为不同的质数

请证明或者证伪当n > 2的时候, 记从1到n-1中，与n互质的正整数的个数为a，那么

2^m | a

只记得欧拉函数，又翻了一下 欧拉函数，有公式结论挺明显的