Purchase Solution

Proofs : GCDs and Primes

Not what you're looking for?

Ask Custom Question

1. (i) Find the gcd (210, 48) using factorizations into primes
(ii)Find (1234, 5678)

2. Prove that there are no integers x, y, and z such that
x^2 + y^2 + z^2 = 999

keywords: greatest comon divisor

Purchase this Solution
Solution Summary

Proofs involving GCDs and Primes are provided. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.

Solution Preview

Problem #1
(i) We use factorizations.
210 = 2*3*5*7
48 = 2*2*2*2*3
Thus gcd(210,48)=2*3=6
(2) To find gcd(1234,5678), we can use the Eucliean algorithm.
5678 = 4*1234 + 742
1234 = 1*742 + 492
742 = 1*492 + ...

Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

View More Free Quizzes
Related BrainMass Solutions

  • Prime proofs

    There are three proofs here that use Fermat's theorem, Wilson's theorem, and binomial expansion.

  • Jacobi Symbols and Proofs

    37827 Jacobi and Legendre Symbols and Proofs 1. Prove that if b and c are odd, then (a/bc)=(a/b)(a/c) 2. Prove that if a==b (mod c), where c is odd, then (a/c)=(b/c) For odd number P=p_1*p_2*...

  • Divisors and relative primes

    Since two consecutive integers can have only a divisor value of k=1 we see that 2a+1 and 4a2+1 are relative primes. The solution provides two short and elegant proofs. Divisors and relative prime functions are provided.

  • Prime simple subgroups

    This provides examples of proofs regarding prime subgroups.

  • Prove that if every even natural number greater than 2 is the sum of two primes, then every odd natural number greater than 5 is the sum of three primes.

    We need to show that m is the sum of three primes. Note that m=(m-3)+3. When m>5, m-3>2 and also m-3 is even. By hypothesis: every even integer greater than 2 is the sum of two primes, there exist two primes p and q such that m-3=p+q.

  • Ring Theory : Associate of a Greatest Common Divisor and Euclidean Rings

    105221 Associate of a Greatest Common Divisor and Euclidean Rings In a Euclidean ring R, any associate of a greatest common divisor is a greatest common divisor. keywords: GCD, GCDs Please see the attached file for the complete solution.

  • Proof of infinite primes

    And the proof is complete. This is a proof regarding infinite numbers of primes.

  • product of primes

    So, we conclude that 64,000,000 is a composite number, and so it can be expressed as a product 64,000,000 = pq with both p and q different from 1 and from 64,000,000 If both p and q are primes, we are done, the number is a product of primes.

  • Quadratic Congruence and Primitive Roots

    Show that if a is aquadratic residue (mod p) and ab=1(mod p) then b is a quadratic residue (mod p) 4. Suppose that p=1+4a, where p and q are odd primes. show that (a/p)=(a/q). I'm attaching the proofs to all the in .docx and .pdf formats.

View More Related Solutions