Ma311 Hw 7

#4. Let tau(n)=the Number of positive divisors of n. Prove that tau(n) is odd if and only if n is a perfect square?

***************************************************** * •

Hint: d is a divisor of n if and only if (n/d) is a divisor of n.

***************************************************** ********* •

Elaborating on the hint: in general, d and n/d form a pair

***************************************************** * •

Let n be a nonsquare positive integer. Then: n =n*1 =a*b =c*d . . . =d*c =b*a =1*n As we can see, since each divisor occurs in pairs, thus the number of divisors must be even. We know there are no repetitions, if not n would be a square number in this case. However, in the case of a square number, factorizations of n include a repetition, say x * x, where x is the square root of n. Thus, the number of positive divisors are odd in this case.

***************************************************** *d divisor of n => n/d divisor of n d < n/d => n > d² => d < sqrt(n) so take all d < sqrt(n) then we have that n/d > d also divisor so they all form pairs

d = n/d => n = d² => n is perfect square here there's no pair !

***************************************************** * 1. The problem statement, all variables and given/known data What are the necessary conditions on n for T(n) {the Tau function} to be odd. 2. Relevant equations Tau function counts the number of divisors of n T(1) = 1, T(p) = 2, and T(p^k) = k + 1

3. The attempt at a solution I have that n cannot be prime, also if n = p^k then k must be even or of the from k = 2c for some c > 0. I cannot figure out how to describe evens with were are multiple primes such as 1x3x7x8 = 231. That number has an even number of divisors but I'm and lost at how to prevent that. I don't understand why k is even OR k=2c. Those are identical conditions.... What is T(xy) for x,y coprime? I meant k is even i.e k =2c... I was just adding more definition. T(xy) for x,y is coprime is an even number of divisors. Thanks. I meant k is even i.e k =2c... I was just adding more definition. T(xy) for x,y is coprime is an even number of divisors. Thanks.No, that's not right. T(xy) for x,y is coprime means T(x)T(y) Is is sufficient to say that T(n) is only odd when n is a perfect square? T(n) is odd if and only if n is a perfect square. Can you prove it? I was just supposed to make a conjecture, but I'll try to work on a proof Assume that n is an odd tau number. Let n = p^a1*p^a2...* p^ak. By the definition of tau number (a1 + 1)(a2 + 1)(a3 + 1)..... (ak + 1) | n. Therefore for any 0 < i < k + 1, ai + 1 is odd, and hence ai is even. Since every prime in the factorization of n is raised to an even power, n is a perfect square. Assume that n is an odd tau number. Let n = p^a1*p^a2...* p^ak. By the definition of tau number (a1 + 1)(a2 + 1)(a3 + 1)..... (ak + 1) | n.What you meant to say was (a_1 + 1)(a_2 + 1)(a_3 + 1)\dots (a_k + 1) = \tau (n) not (a_1 + 1)(a_2 + 1)(a_3 + 1)\dots (a_k + 1) | nTherefore for any 0 < i < k + 1, ai + 1 is odd, and hence ai is even. Since every prime in the factorization of n is raised to an even power, n is a perfect square.The question only asked you to find a necessary condition, and you've done this. But the stuff you've said above goes both ways, so it's actually a sufficient condition as well.

Proposition 1. If n = (p_1)^(a_1)*(p_2)^(a_2)*…*(p_k)^(a_k) then tau(n) = (a1 + 1)(a2 + 1)(a3 + 1)… (ak + 1). Theorem 2. Any odd tau number is a perfect square.

Proof. Assume that n is an odd tau number. Let n = (p_1)^(a_1)*(p_2)^(a_2)*…*(p_k)^(a_k). By Proposition 1 and the definition of tau number (a1 + 1)(a2 + 1)(a3 + 1) : : : (ak + 1) divides n. Therefore for any 0 < i < k + 1, ai + 1 is odd, and hence ai is even. Since every prime in the factorization of n is raised to an even power, n is a perfect square.

************************************************************* ***********

# Proof of the Day!! Can someone please Prove that if d divides m, and e divides n, then gcd(d,e) divides gcd(m,n)? ***************************************************** ********* •

Let a = gcd(d,e). => a divides d and a divides e. In what follows, I assume "divides" is transitive. If you don't have this theorem, then prove it. Since a divides d and d divides m, a divides m. Since a divides e and e divides n, a divides n. Hence a divides both m and n. It follows that a=gcd(d,e) divides gcd(m,n).

***************************************************** * #1. Does anyone know a proof of the following (dealing with Number Theory)? If [(a^n) - 1] is a prime then a = 2 and n is a prime. ***************************************************** * •

You left out an important detail. If n=1, then there are a lot of possible values for a. However, if we force n>1, then the following holds: a^n - 1 is a prime number, so we may restrict a>1. Now factor a^n - 1: a^n - 1 = (a-1)(a^(n-1) + a^(n-2) + ... + a + 1)

Since a>1, the factor on the right must be greater than 1. This forces a-1 = 1. Thus a=2. Assume n is composite. Then n=s*t for integers s,t>1. Again, looking at the factorization, we see: 2^n - 1 = (2^s)^t - 1 = (2^s - 1)(2^(s*(t-1)) + 2^(s*(t-2)) + ... + 2^s + 1) Both of these factors are obviously integers larger than 1. This would show that 2^n - 1 is not prime. Hence our assumption that n is composite is wrong. Since we know that n>1, n must be prime.

***************************************************** ********* Theorem. If for some positive integer n, 2n-1 is prime, then so is n. Proof. Let r and s be positive integers, then the polynomial xrs-1 is xs-1 times xs(r-1) + xs(r-2) + ... + xs + 1. So if n is composite (say r.s with 1<s1. Since x-1 divides xn-1, for the latter to be prime the former must be one. This gives the following. Corollary. Let a and n be integers greater than one. If an-1 is prime, then a is 2 and n is prime. Usually the first step in factoring numbers of the forms an-1 (where a and n are positive integers) is to factor the polynomial xn-1. In this proof we just used the most basic of such factorization rules, see [BLSTW88] for some others.

***************************************************** ********* #2 and #3) M, n, d are positive integers. Assume that gcd(m,n) = 1. Assume further that d divides m*n. Using this info? A) Prove that there exist positive integers d_1 and d_2 such that d = (d_1 * d_2) and d_1 divides m and d_2 divides n. an example of this is let m=9, n=49, m*n=441, then 21 divides 441, and d_1=3, and d_2=7 B) Prove that d_1 and d_2 are unique.

• •

7 hours ago - 3 days left to answer.

Additional Details 6 hours ago

#3 C) Using the proof of the previous A & B prove the following: If th gcd(m,n) = 1, then Sigma(m,n) = Sigma(m) * Sigma(n)

***************************************************** ********* It's tough to know what proof works for you without knowing which theorems you have and haven't had in class. That said: If you've had unique factorization into primes, then the basic idea is that every prime in d's factorization divides m or n, but not both. So you break up d into the part that fits into m and the part that fits into n. This method of proof also gives uniqueness. In pretty much any approach to the proof, you wind up showing that d = gcd(d,m) * gcd(d,n). That's the central idea.

***************************************************** *********