9.6 Coursework Sheet 5
Hand in your solutions in the appropriate way by Monday, 13 November 2023, 19:00.
Exercise 1
Prove the following statement: The cube root of \(2\) is irrational. [HINT: The opposite of what we want to prove is that there are integers \(a\), \(b\) with \(2a^3=b^3\). Analyse the prime factorisations on both sides of this.]
Exercise 2
- Factorise 5963 into a product of two primes.
- You are given a 100 digit number and told that it is the product of two primes. If you factorise it, using whichever method you used in part (a), then roughly how many calculations do you have to perform?
(Compare with Q6, sheet 4).
Exercise 3*
Let \(p_n\) denote the \(n^{\text{th}}\) prime. Let \(a,b\) be positive integers and let \(n\) be large enough so that there exists non-negative integers \(e_1,\ldots, e_n, f_1,\ldots, f_n\) such that \[ a = p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n},\;\; b = p_1^{f_1}p_2^{f_2}\ldots p_n^{f_n}. \] For example if \(a=63, b=50\) then \[ a = 2^03^25^07^1, b = 2^13^05^27^0. \] Show that \[ \gcd(a,b)=p_1^{g_1}\ldots p_n^{g_n},\;\; \text{lcm}(a,b)=p_1^{h_1}\ldots p_n^{h_n}, \] where \(g_i=\min(e_i,f_i), h_i = \max(e_i,f_i)\), for \(1\le i\le n\).
Let \(e,f,g\) be non-negative integers. Show that \(\min(e,\max(f,g)) = \max(\min(e,f),\min(e,g))\).
Let \(a,b,c \in\mathbb Z\). Show that \[ \gcd(a,\text{lcm}(b,c)) = \text{lcm}(\gcd(a,b),\gcd(a,c)). \] Hence, or otherwise, show that \(\gcd\) is a multiplicative function, i.e. for all \(a,b,c \in\mathbb Z\) with \(b\) and \(c\) coprime, \[ \gcd(a,b)\gcd(a,c) = \gcd(a,bc). \]
Exercise 4
You are given that \(a^b-1\) is a prime number, for some \(a,b>1\).
- Show that \(a=2\).
- Show that \(b\) is a prime.
Hint: You may find it useful to use the identity: \((x-1)(1+x+x^2+\cdots+ x^{n-1})=x^n-1\).
A prime number of this form is called a Mersenne prime. For information on the hunt for these primes go to:
[http://en.m.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search]