Difficulty: Intermediate | Prerequisites: Basic probability, indicator variables, Chernoff bounds, modular arithmetic, GCD
This material covers two distinct topics from the same homework. The random graph section introduces the Erdos-Renyi model G(n,p) and asks you to estimate the edge probability p using only a degree oracle, then bound the estimate's error with Chernoff bounds. The number theory section covers Euler's totient function and proves a foundational result: an element of Z_n has a multiplicative inverse if and only if it is coprime to n. Both topics exercise the same underlying skills: setting up the right random variables or algebraic structure, then applying the appropriate bound or algorithm.
In a random graph G(n,p), the expected number of edges is C(n,2) * p and the expected degree of any vertex is (n-1)p. You can estimate p by sampling degrees and dividing by (n-1). Separately, Euler's totient function phi(n) counts integers coprime to n, and the elements with modular inverses in Z_n are exactly the ones coprime to n, proved via the Extended Euclidean algorithm.
G(n,p) / Erdos-Renyi random graph
A random undirected graph on n vertices where each possible edge is included independently with probability p. Think of it as: flip a biased coin for every pair of vertices, and draw the edge if heads.
Expected degree
For any vertex v in G(n,p), the expected degree is (n-1)p, since v has n-1 potential neighbours and each edge exists independently with probability p.
Degree oracle (D)
A black box that picks a random vertex v from G(n,p) and returns deg(v). You cannot inspect the graph directly; D is your only source of information about edges.
Euler's totient function, phi(n)
The count of integers m with 1 <= m < n that are coprime to n (i.e. gcd(m, n) = 1). In simple terms, it counts how many numbers less than n share no prime factors with n.
Z_n (integers mod n)
The set {0, 1, 2, ..., n-1} with arithmetic performed modulo n.
Z_n^ (multiplicative group mod n)*
The subset of Z_n consisting of elements that have a multiplicative inverse modulo n. In simple terms, a is in Z_n^* if there exists some b such that a * b is congruent to 1 (mod n).
Coprime / relatively prime
Two integers a and n are coprime if gcd(a, n) = 1. They share no prime factors.
Extended Euclidean algorithm
An algorithm that, given integers a and n, finds integers x and y such that ax + ny = gcd(a, n). When gcd(a, n) = 1, this gives x as the modular inverse of a mod n. Think of it as: a constructive proof that coprimality implies invertibility.
Modular inverse
For a in Z_n, the element b such that a * b = 1 (mod n). Exists if and only if gcd(a, n) = 1.
Expected number of edges in G(n,p)
There are C(n,2) = n(n-1)/2 possible edges. Each is included independently with probability p. By linearity of expectation, the expected number of edges is n(n-1)p/2.
Expected degree of a vertex
A vertex v has n-1 potential neighbours. Each edge to a neighbour exists with probability p, independently. So E[deg(v)] = (n-1)p.
Estimating p from the degree oracle
Algorithm: call the degree oracle D a total of k times, getting degrees d_1, d_2, ..., d_k. Output p' = (d_1 + d_2 + ... + d_k) / (k(n-1)).
Each d_i / (n-1) is an unbiased estimator of p (since E[d_i] = (n-1)p for a random vertex).
Strictly, the degrees are not sums of independent indicators (since the vertices are random and edges may overlap). However, each oracle call is an independent experiment, so d_1/(n-1), ..., d_k/(n-1) are i.i.d. with mean p.
E[p'] = p, so p' is an unbiased estimator.
Bounding P[p' >= 3p] using Chernoff bounds
We want P[p' >= 3p]. Since E[p'] = p, this asks for the probability the estimate is at least 3 times the true value.
Set the deviation: p' >= 3p means p' - p >= 2p, so epsilon = 2p.
Apply the upper-tail Chernoff bound (adapted for this setup): P[p' >= p + 2p] <= e^(-2(2p)^2 k) = e^(-8p^2 k).
The exact form depends on how you model the indicator variables within each degree query. The bound is e^(-8p^2 k) or a related expression depending on the version of Chernoff used.
Euler's totient: proving |Z_n^*| = phi(n)
The claim: a in Z_n has a multiplicative inverse mod n if and only if gcd(a, n) = 1.
Forward direction: gcd(a, n) = 1 implies a has an inverse
By the Extended Euclidean algorithm, if gcd(a, n) = 1, there exist integers x, y with ax + ny = 1.
Reducing mod n: ax is congruent to 1 (mod n).
So x (mod n) is the multiplicative inverse of a.
Reverse direction: a has an inverse implies gcd(a, n) = 1
Suppose ab is congruent to 1 (mod n) for some b. Then ab = 1 + kn for some integer k, i.e. ab - kn = 1.
Any common divisor d of a and n must also divide ab - kn = 1.
Therefore d = 1, so gcd(a, n) = 1.
Conclusion
The elements of Z_n with multiplicative inverses are exactly those coprime to n. Since phi(n) counts the integers in {1, ..., n-1} coprime to n, we have |Z_n^*| = phi(n).
Students sometimes count n^2 possible edges instead of n(n-1)/2. Remember: the graph is undirected (so {u,v} = {v,u}) and has no self-loops (so u != v).
When estimating p from the degree oracle, students forget to divide by (n-1), not n. Each vertex has n-1 potential neighbours, not n.
For the totient proof, students try to prove the forward direction by brute force rather than using the Extended Euclidean algorithm. The EEA gives you the inverse constructively, which is exactly what the hint asks for.
Students sometimes confuse "coprime to n" with "prime." The number 4 is coprime to 9 (gcd(4,9) = 1) even though 4 is not prime.
Expected value calculations in random graphs (expected edges, expected degree) are routine exam questions. Know the formula E[edges] = C(n,2) * p cold.
The degree-oracle estimation problem tests whether you can design an unbiased estimator and then apply Chernoff bounds. This pattern (design estimator, then bound its error) recurs across the course.
The totient function result |Z_n^*| = phi(n) is foundational for RSA cryptography, which appears later in EECS 376. The Extended Euclidean algorithm is also how you compute RSA private keys.
The if-and-only-if structure of the totient proof (forward: EEA gives inverse; reverse: inverse implies gcd = 1) is a standard proof pattern worth practising.
Fill in the blank: The expected number of edges in G(n,p) is ____. (n(n-1)p/2)
True or False: E[deg(v)] = np for a vertex v in G(n,p). (False, it is (n-1)p.)
Fill in the blank: phi(9) = ____. (6)
True or False: 6 has a multiplicative inverse mod 9. (False, gcd(6,9) = 3 != 1.)
Fill in the blank: If gcd(a,n) = 1, the Extended Euclidean algorithm finds x,y such that ax + ny = ____. (1)
Q: What is the expected number of edges in G(n,p)?
A: There are C(n,2) = n(n-1)/2 possible edges. Each is included with probability p independently. By linearity of expectation, the expected count is n(n-1)p/2.
Q: Describe an algorithm using the degree oracle D that produces an unbiased estimate of p.
A: Call D a total of k times, obtaining degrees d_1, ..., d_k. Output p' = (1/k) * sum(d_i / (n-1)). Since E[d_i] = (n-1)p for a random vertex, E[d_i/(n-1)] = p, so E[p'] = p.
Q: Prove that if gcd(a,n) = 1, then a has a multiplicative inverse mod n.
A: By the Extended Euclidean algorithm, there exist integers x and y such that ax + ny = 1. Reducing modulo n, ax is congruent to 1 (mod n). So x mod n is the inverse of a.
Q: Prove that if a has a multiplicative inverse mod n, then gcd(a,n) = 1.
A: Suppose ab is congruent to 1 (mod n). Then ab = 1 + kn for some integer k, so ab - kn = 1. Any common divisor of a and n divides both a and n, hence divides ab and kn, hence divides ab - kn = 1. So gcd(a,n) = 1.
Q: Use Chernoff bounds to upper-bound P[p' >= 3p].
A: E[p'] = p, and p' >= 3p means p' - p >= 2p. Applying the upper-tail Chernoff bound with epsilon = 2p: P[p' >= p + 2p] <= e^(-2(2p)^2 k) = e^(-8p^2 k). The bound decreases exponentially in k.
The random graph material connects directly to the Chernoff bound and Monte Carlo estimation topics from this same homework: you design an estimator, then bound its error probabilistically. The Erdos-Renyi model is also foundational in network science and algorithm analysis on random inputs.
Euler's totient function connects forward to RSA encryption, where the security of the scheme rests on the difficulty of computing phi(n) without knowing n's factorisation. The Extended Euclidean algorithm is used to compute both modular inverses and RSA private keys.
Erdos-Renyi model, G(n,p), random graph, expected degree, expected edges, degree oracle, unbiased estimator, Chernoff bound, Euler's totient function, phi(n), coprime, relatively prime, modular inverse, multiplicative inverse, Z_n star, Extended Euclidean algorithm, GCD, RSA, number theory, EECS 376, Foundations of Computer Science, University of Michigan