Some numbers m look like prime numbers, in the sense that the conclusion of Ferm

Question

Some numbers m look like prime numbers, in the sense that the
conclusion of Fermat's Theorem holds for m, namely,
For all a coprime to m,
a^{m-1} = 1 (mod m) (here the equal sign means congruent to..I couldn’t type the congruence sign)
Let's call m an “almost prime" if the conclusion of Fermat's Theorem
holds for m. It turns out that if a number m is not almost prime, then it's pretty
easy to tell. The proof is to use ideas connected with Lagrange's Theorem.

Using the idea of the proof of Lagrange's Theorem, explain why
it is that if m is not an almost prime, then there are at least as many
numbers a with 0 < a < m so that a^{m-1} is not congruent to 1 modulo
m as there are numbers a so that ^{am-1} is congruent to 1 modulo m.
(Think cosets.)

Can anybody please help me with this...I've been working on this for hours and still couldn't figure it out.

Explanation / Answer

Hii Buddy I answered this in you yahoo page also get some more like this dude :) i) Let S be the set of [a] such that [a]^{m-1} = [1]. Clearly [1]^{m-1} = [1], so the identity is in S. Suppose a is in S, then [a^(-1)]^{m-1} = [a]^{-(m-1)} = ([a]^{m-1})^{-1} = [1]^{-1} = [1]. So the inverse of a is in S. Suppose a and b are in S. Then [ab]^{m-1} = ([a][b])^{m-1} = [a]^{m-1}[b]^{m-1} = [1][1] = [1]. So ab is in S. Therefore S is a subgroup of Um. ii) Notice that the definition of almost prime can be stated as: S = Um (where S is defined as in (i)). So if m is not an almost prime then S is a proper subgroup of Um. This means that S has a coset in Um that is distinct from S. Call this coset T. Using ideas in Lagrange's Theorem, it follows that S and T have the same size. Now, the elements a with 0

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.