Mathematics for Computer Science

8.13. References 309

(c)Call a number from 0 to 174powerfuliff some positive power of the number
is congruent to 1 modulo 175. What is the probability that a random number from
0 to 174 is powerful?

(d)What is the remainder of.12/^482 divided by 175?

Problem 8.71. (a)Calculate the remainder of 3586 divided by 29.

(b)Part (a) implies that the remainder of 3586 divided by 29 is not equal to 1. So
there there must be a mistake in the following proof, where all the congruences are
taken with modulus 29:

1 6 3586 (by part (a)) (8.47)

 686 (since 35 6 .mod29/) (8.48)

 628 (since 86 28 .mod29/) (8.49)

 1 (by Fermat’s Little Theorem) (8.50)

Identify the exact line containing the mistake and explain the logical error.

Problem 8.72.
Give counterexamples for each of the statements below that are false. All variables
range over the integers,Z.

(a)For allaandb, there arexandysuch that:axCbyD 1.

(b)gcd.mbCr;b/Dgcd.r;b/for allm;randb.

(c)kp^1 1 .modp/for every primepand everyk.

(d)For primesp¤q,.pq/D.p1/.q1/, whereis Euler’s totient function.

(e)Ifaandbare relatively prime tod, then

Œacbcmoddç IMPLIES Œabmoddç: