1
$\begingroup$

I'm trying to understand 100% intuitively and rigorously ( at the same time ) almost all facts in basic number theory. I'm going really slow-paced and at the moment i didn't reach primes and unique factorization. I was able to gain full intution and understanding ( while also knowing how to prove ) about basic properties of divisibility relation ( poset with Z* ), euclidean division, euclidean algorithm, bezout identity, the fact that every common divisor divides the gcd, the "linearity" of gcd ( gcd(ma,mb) = m.gcd(a,b) ) .
But now there are some theorems that i'm struggling to 100% intuitively understand.

For instance, the fact that if gcd(a,d) =1 and d | ab, then d | b.
I know how to formally prove that.
If gcd(a,d) =1 is the least positive linear combination of a and d, and this is obtained with some pair (x,y), then ax + dy = 1.
But while (x,y) is the "minimal pair" for a and y and gives gdc(a,b) as result, it is also a "minimal pair" for ab and db and gives b.gcd(a,b) as result. So gcd(ab,db) = b, and if the theorem is saying that d is a common divisor of ab and db ( because it divides ab, and clearly divides db ) , then it must divides the gcd of (ab,db), that is, b.
Or more shortly, there exists x,y s.t ax + dy = 1 , which implies
bax + dby = b . If d | ab, since it divides bd, it has to divide b.

But i want to get to the point where i see intuitively why this is true, not having to go into the mentioned proof. From that proof, i can only get that if gcd(a,d)=1, common divisors of the b-multiple of (a,d) , d in the case of the theorem, must also divide the gcd of the b-multiple of (a,d) , that is, must divide b.

But i can't get past that level to increase my intuition. I still don't know why if some d divides ab, and it doesnt divide a ( gcd(a,d)=1 ) , it has to divide b.

Is there any way, point of view or anything essential that doesnt use unique factorization and primes that i'm not seeing that can be considered when thinking about this theorem , maybe some intuitive corollaries of the topics i said i understood, that enables us to understand the truth of this theorem ( and related theorems as well ) autoamtically and intuitively ?

But if there isn't any way to see that more intuitively withouth using unique prime factorization and primes, then please to use it.
Thanks a lot in advance !

$\endgroup$
3
  • 1
    $\begingroup$ I think that I understand that law very intuitively (I knew it when I was a child, although I hadn't the slightest idea about how to prove it). But my intuition was strongly based on the unique factorization. Your question is for me like asking about why things fall and asking for an answer that does not mention the gravity, if you understand me. But, well, this is not a proof :-) Maybe sombebody has this intuition. $\endgroup$
    – ajotatxe
    Apr 6, 2014 at 0:21
  • $\begingroup$ Yeap :).I acknowledge that further intuition might require understanding unique factorization and primes, but was just trying to see if theres some other way around it. $\endgroup$
    – nerdy
    Apr 6, 2014 at 0:50
  • 1
    $\begingroup$ One can give some intuitive explanation, but it will be some form of unique factorization theorem. Let me attempt: there are three kinds of factors (not mutually exclusive) for the product number $ab$; (i) those that are factors of $a$, (ii) those that are factors of $b$, (iii) those factors that are product of a factor of $a$ and a factor of $b$. (We can make it precise so that $1,a,b$ are not counted multiple times.) Now if $d$ divides $ab$ and is not of type (i) or type (iii) it has to be of type (ii). $\endgroup$ Apr 6, 2014 at 1:19

0

You must log in to answer this question.

Browse other questions tagged .