I do not know how to prove number 19. Please help me thank you! Verifying congru

Question

I do not know how to prove number 19.

Please help me thank you!

Verifying congruences such as those that occur in Fermat's and Euler's theorems requires the computation of a large power of a (mod m). To find a^(mod m), one could successively compute a, a^2, ..., a^(mod m). To find a^(mod m), one reductions (mod m). Show how this can be reduced to c log r such operations (where c is some not-very-interesting constant) by utilizing the base-2 representation of r, r = epsilon_0 + epsilon_1 middot 2 + ... + epsilon_m 2^m, each epsilon_ = 0 or 1. Show that for all a and b, and for p prime, a^p + b^p = (a + b)^p (mod p). Generalize to arbitrarily many terms. Take a = b = ... = 1 to obtain an additional proof of Fermat's theorem. Prove the following partial converse of Fermat's Theorem: if there is an a for which a^m - 1 = 1 (mod m), while none of the congruences a^(m - 1)/p = 1 (mod m) holds, where p runs over the prime divisors of m - 1, then m is prime. (The first congruence alone is not sufficient; for example, 4^2 = 1 (mod 15) so 4^14 = l (mod 15).) If you have a 10-digit-display calculator, use this to show that f_4 = 2^2 + 1 is prime. Prove that if (a, b) = d, then phi (ab) = d phi (a) phi (b)/phi (d). Show that if n > 1, then the sum of the positive integers less than n and prime to n is n phi (n). Show that if d | n, then phi (d) | phi (n). Show, perhaps with the help of Theorem 3.8, that phi (n) = 2 (mod 4) if and only if n = p^or 2p^, where p is a prime = 3 (mod 4) and a > 0. Conclude that (a) the phi-function does not assume the value 14; (b) if the number of n lessthanorequalto N such that 4 times phi (n) is f (N), then f (N)/N rightarrow 0 as N rightarrow infinity. Let f (x) e Z [x], and for n greaterthanorequalto 1 let Psi_f (n) = Psi (n) denote the number of values of k, with 1 lessthanorequalto k lessthanorequalto n, such that (f (k), n) = 1. a) Show that Psi is multiplicative. b_ Show that Psi (n) = n Product_p |n (1 - b_p/p), where b_p = p - Psi (p) is the number of multiples of p among f (l), f (2), ..., f (p). How many reduced fractions r/s are there with 0 lessthanorequalto r 1 is odd and ord_m a = 2t, then a^t = - 1 (mod m). Show that this need not be true if 2|m. Show that if m is larger than 1 and a^t = - 1 (mod m), then ord_m a = 2u and t = for some integers u and k.

Explanation / Answer

19. Given ordm a = 2t

=> a2t 1 mod m

=> m divides a2t-1

=> m divides (at-1) (at+1)

Note that at+1 = at-1 + 2. There is no odd number greater than 1 that can divide both as their difference is only 2. So m can divide only one of them.

If m divides at-1, then

at 1 mod m

and so ordm a = t and not 2t since t<2t.

So m does not divide at-1. It divides at+1.

=> at -1 mod m

If 2|m, Since a2t 1 mod m, a2t and hence a is odd.

at the step

m divides (at-1) (at+1)

m can divide both at-1 and at+1 as both are even numbers.

So the earlier result need not apply.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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