Let A, B Z. Knowledge of the prime power factorization for A and B simplifies ma

Question

Let A, B Z. Knowledge of the prime power factorization for A and B simplifies many types of computation. Let: A = p1^a1 . . . pm^am and B = p1^b1 . . . pm^bm . where p1, . . . , pm are distinct primes and a1, . . . , am, b1, . . . , bm are nonnegative integers (zero is allowed, so it is not exactly a prime power factorization, but very close).

Using expressions for A and B above:

(1) Write a similar expression for A · B.

(2) Write a condition for B | A.

(3) Assuming that B | A find a similar expression for A B .

(4) Find an expression for gcd(A, B).

(5) Find an expression for lcm(A, B).

Explanation / Answer

(1) A.B = p1a1+b1p2a2+b2....... pmam+bm

(2) If a1 >= b1, a2 >=b2.....am>=bm, then B|A.

(3) A/B = p1a1-b1p2a2-b2....... pmam-bm

(4) Since all factors are primes, they all divide A and B. The gcd depends on whichever is smaller, a or b.

If a is greater, the gcd has power b. Else the gcd has power a.

The smallest of two numbers a and b

= [ (a+b) - |(a-b)| ] / 2

where |(a-b)| is the absolute (positive or zero) value of a-b.

=> gcd(A,B) = p1[ (a1+b1) - |(a1-b1)| ] / 2....... pm[ (am+bm) - |(am-bm)| ] / 2

(As per Chegg policy only four sub questions will be answered. You need to post a new question for the fifth answer. Or you can follow the method used to find gcd.)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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