Please show detail on these 3 questions! 1.) Solve the congruence system, 2x+3y

Question

Please show detail on these 3 questions!

1.) Solve the congruence system,

2x+3y congruent to 1 (mod11)

x+4y congruent to 4 (mod 11)

2.) Let n be a natural number. We compute (empty set (d)) of every divisor d of n, then add up all these numbers. What is the sum? (Experiment, formulate a conjecture, and prove it)

Note : we denote by (empty set (n)) the number of those numbers that are not larger than n and are relatively prime to n.

3.) We add up all the positive integers smaller than n and relatively prime to n. What do we get?

Explanation / Answer

1)

First :
2x + 3y = 1 [11]
2x+ 4y = 8[11] (by multiplying by 2 the second line)
So y = 7[11] (by substracting),

=> y = 7+11n2 for some n2


Similarly :
8x+12y = 4[11]
3x+12y = 12 [11] =1[11]
so 5x = 3[11]
=>   5x = 3 + 11n3 for some n3
=>   5x = 25 +11(n3-2)
=>   x = 5+11n1 for some n1

So the solution is x = 5+11n1 and y=7+11n2 for n1,n2 integers.

2) The function you name is the totient function, i'll call it phi(n).

Let n = 8 , d=1,2,4,8 phi(1)=1,phi(2)=1,phi(4)=2,phi(8)=4 and 4+2+1+1=8=n

So we assume that sum(over all divisors d of n)phi(d) = n , we will prove that.

Note that {d / d is a divisor of n} = {n/d / d is a divisor of n}

So sum(over all divisors d of n)phi(d) = sum(over all divisors d of n)phi(n/d).

Let's partition the set {1,2,3,...,n} into subsets according to each element's greatest common divisor with n.
Each subset of {1,2,3,...,n} will be called Q(g), the set of all integers between 1 and n inclusive, such that gcd(x,n) = g.
The Q(g) sets don't overlap, and their union is {1,2,3,...,n}, so the sum of the cardinality of the Q(g) sets is n.

Also, there is a one-to-one correspondence between the elements of Q(g) and the proper coprimes of n/g, which completes the proof.

3)

You are interested in S=sum(0<=m < n / gcd(m,n) =1} m

Let's take again n=7, gcd(d,n)=1 with d=1,2,3,4,5,6 and 1+2+3+4+5+6=6*7/2=phi(n)*n/2

If k in {1,...,n?1} is relatively prime to n, so is n?k, so the integers that you

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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