Question on theorem of arithmetic euclid's algorithm

Click For Summary

Homework Help Overview

The discussion revolves around the theorem of arithmetic and the Euclidean algorithm, specifically focusing on a problem that involves understanding prime factorizations and divisibility criteria.

Discussion Character

  • Exploratory, Conceptual clarification, Mathematical reasoning

Approaches and Questions Raised

  • Participants explore the possibility of using induction as a proof method, while others express skepticism about its applicability. There is a suggestion to compare prime factorizations of two numbers and to analyze the implications of divisibility on the exponents of primes in these factorizations.

Discussion Status

The conversation is ongoing, with participants seeking clarification on the relationship between divisibility and prime factorization. Some guidance has been offered regarding the conditions of divisibility, but there is no consensus on the best approach yet.

Contextual Notes

Participants are grappling with the definitions and implications of divisibility in the context of prime factorization, indicating that there may be gaps in understanding the foundational concepts involved.

singedang2
Messages
25
Reaction score
0
http://img143.imageshack.us/img143/7461/divsuu6.jpg
i know this question has to do with theorem of arithmetic and euclidean algorithm, but i don't even know where to start. help pls! thank you!
 
Last edited by a moderator:
Physics news on Phys.org
How about an argument using induction?
 
i don't think this can proven with induction... any other comments?
 
Try comparing prime factorizations of a and b. Suppose a prime p appears as p^k in the prime factorization of a and as p^m in the prime factorization of b.

what do those divisbility critrea tell you about m and k?
 
tell me more about this... gahhh i don't quite get it.
 
Start with the first condition, a|b^2. You should be able to come up with an inequality for k and m from this.

How does divisibility relate to the exponents in a prime factorization?
 

Similar threads

Replies
6
Views
1K
  • · Replies 13 ·
Replies
13
Views
1K
Replies
28
Views
2K
Replies
86
Views
3K
  • · Replies 16 ·
Replies
16
Views
4K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 11 ·
Replies
11
Views
1K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 64 ·
3
Replies
64
Views
4K
  • · Replies 13 ·
Replies
13
Views
3K