Politically Correct Moduli (Posted on 2005-09-03)

	Submitted by McWorter
Rating: 4.0000 (2 votes)
Solution:	(Hide)
Answer: powers of a single prime. If x^2-3x+2 is congruent 0 modulo n=p^k, where p is a prime, then, since x-1 and x-2 are relatively prime, p divides only one of x-1 and x-2. Hence x is congruent 1 or 2 modulo n. On the other hand, let n=ab, where a and b are relatively prime and both greater than 1. Then there exist integers u and v such that au+bv=1. Set x=au+1. Then x=-bv+2 as well. Hence x-1 is divisible by a and x-2 is divisible by b. Thus the product, x^2-3x+2, is congruent 0 modulo n=ab. The integer x=-bv+2 is not congruent to 1 modulo n because this implies bv is congruent 1 modulo n, contradiction. Similarly, x is not congruent 2 modulo n. Hence x^2-3x+2 has at least three incongruent roots modulo n=ab.

	Subject	Author	Date
	Puzzle Thoughts	K Sengupta	2023-07-28 01:26:34
	re(7): Proof	McWorter	2005-09-04 05:39:40
	re(6): Proof	Richard	2005-09-04 04:38:50
	re(5): Proof	McWorter	2005-09-04 03:51:18
	re(4): Proof	Richard	2005-09-04 01:04:08
	re(3): Proof	McWorter	2005-09-03 23:38:59
	re(2): Proof	Richard	2005-09-03 23:09:09
	re: Proof	McWorter	2005-09-03 21:20:24
	Proof	Tristan	2005-09-03 20:55:03
	bases that work; and those that don't	Charlie	2005-09-03 18:22:16
	re: I think the answer is...	Richard	2005-09-03 17:52:56
	I think the answer is...	Tan Kiat Chuan	2005-09-03 16:39:15