Register to reply

Some divisibility questions

by AlbertEinstein
Tags: divisibility
Share this thread:
AlbertEinstein
#1
Oct7-06, 12:08 PM
P: 113
Hi,

I am going through the book on number theory by ivan niven. well its tough book though, and i am stuck with problems in the first topic divisbility.Hope some help.

1. prove that a|bc if and only if a/(b,c)|c where (b,c) is the lcm of b and c.

2. Prove that there are no positive integers a,b,n>1 such that
[tex](a^n-b^n)|(a^n+b^n)[/tex].

In the first one i have no clue how to start the proof. any hint will be appreciated.

In the second one i had the following proof:
if posssible let there be a +ve integer k such that
[tex]\frac{a^n-b^n}{a^n+b^n} = k[/tex]
clearly k is not equal to 1, since then b=0 which is contradictory.
applying compodendo and dividendo to the above frac we write
(a/b)^n = (k+1)/(k-1) ---------------------------(1)
now (k+1)/(k-1) can be written as (1 + 2/(k-1) )
It can be directly checked that k=2,3 do not satisfy (1)
for k>3, (k+1)/(k-1) lies between 1 and 2 and hence cannot be a perfect nth number. this contradiction gives the desired proof.

well,are my lines of reasoning true?
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
Hurkyl
#2
Oct7-06, 12:22 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,099
lies between 1 and 2 and hence cannot be a perfect nth number.
Sure it can. 121/100 is the perfect square of 11/10, for example.
AlbertEinstein
#3
Oct7-06, 12:37 PM
P: 113
Ok, i didn't check that .Sorry, but I don't know how to attack the problem.
Any hints?

matt grime
#4
Oct7-06, 02:26 PM
Sci Advisor
HW Helper
P: 9,398
Some divisibility questions

Rule 1: never write things like x/2 in number theory unless you know before hand that x is divisible by 2. Divisibility is not about quotients, it is about multiplication.

We may suppose that a and b are coprime, and that a^n-b^n =/=1 since n=/1. Now think about things.....
AlbertEinstein
#5
Oct7-06, 08:29 PM
P: 113
sorry matt,I am not able to see what conclusions will i get on those assumption. a little more help, please.
thanks.
Office_Shredder
#6
Oct8-06, 02:16 AM
Emeritus
Sci Advisor
PF Gold
P: 4,500
EDIT: Never mind, I'm retarded
matt grime
#7
Oct8-06, 02:43 AM
Sci Advisor
HW Helper
P: 9,398
Quote Quote by AlbertEinstein
sorry matt,I am not able to see what conclusions will i get on those assumption. a little more help, please.
thanks.

I wasn't expecting you to 'see' conclusions just like that. You're supposed to play around with things. Do you see that you may assume a and b are coprime irrespective of why that may be useful? Do you see that we may assume that a^n-b^n does not equal 1? Given we may assume that, what can we do that contradicts these assumptions if a^n-b^n divides a^n+b^n? (Note, this is a very useful idea in general.)

Let's try a different tack. x divides y means that hcf(x,y)=x. Remember the proof of the euclidean algorithm too. hcf(x,y)=hcf(x,x+y)=hcf(x,x-y).
Muzza
#8
Oct8-06, 08:58 AM
P: 696
1. prove that a|bc if and only if a/(b,c)|c where (b,c) is the lcm of b and c.
This is problem 43 in chapter 1, and it actually wants you to prove that a|bc <=> a/(a, b)|c. Also, (a, b) denotes the gcd of a and b. The lcm is often written [a, b]. This problem can be solved by (for example) writing things out in terms of the prime factorizations of a, b, c.
AlbertEinstein
#9
Oct8-06, 10:14 AM
P: 113
first of all sorry for the typo here (b,c) represents the hcf of b and c.

I did the following:If a^n-b^n divides a^n+b^n then
(a^n-b^n , a^n+b^n) = a^n-b^n
now since (x,y)=(x,x+y)=(x,x-y)
we have [tex] ((a^n-b^n),(a^n+b^n))=((a^n-b^n),2 a^n)=((a^n-b^n),2 b^n)[/tex]
This implies that [tex] a^n = m b^n [/tex]
therefore [tex]\frac{a^n+b^n}{a^n-b^n} = \frac{m+1}{m-1}[/tex]
since the last fraction is not an integer for m=/=2,3. we arrive at a contradiction.

Hoping to be correct
matt grime
#10
Oct8-06, 02:04 PM
Sci Advisor
HW Helper
P: 9,398
Never ever write fractions like that, only ever write integers. ONly ever work in terms of things that divide some thing, never rational numbers.

If p is some prime that divides a^n-b^n, and a^n+b^n, then it divides which two other things you've written there. Now, remember we can assume that a and b a coprime...
AlbertEinstein
#11
Oct9-06, 05:52 AM
P: 113
Never ever write fractions like that, only ever write integers. ONly ever work in terms of things that divide some thing, never rational numbers.
Matt, please explain the reason for this with some more detail, I am not able to understand it.

then it divides which two other things you've written there
Are they 2a^n and 2b^n ?

assume that a and b a coprime...
But what if they are not co-prime?
matt grime
#12
Oct9-06, 06:14 AM
Sci Advisor
HW Helper
P: 9,398
Matt, please explain the reason for this with some more detail, I am not able to understand it.

Ontological commitment? That's one philosophical reaon to do this. Another is that it makes you prove things for the correct reason, rather than invoking the rational numbers for benefit what-so-ever. Divisibility is not about dividing things it is about multiplying things: x divides y means there is a z with zx=y. It is good practice, and makes you think about these things in the 'correct' way. I.e. that something is true for reasons that are apply to the objects in question, not because something is not true about some object that a priori does not exist. You are working in the integers. The rational numbers should not be something you invoke when thinking about these things. This assures us amongst other things that you are working the the right notions, and that the result applies to other situations in which it might be nonsensical to talk about rationals.


But what if they are not co-prime?
I asked you if you understood why we may assume they are coprime, and you didn't answer.... Prove that if we can find an example, we can find an example with a,b coprime. If we can we may as well assume they are and try to get a contradiction from that assumption. Given that you can assume they are coprime, then above has shown that any prime divisor of a^n-b^n is a divisor of 2a^n and 2b^n, thus since a and b are coprime a^n-b^n equals 1 or 2, both of which are impossible: (x+1)^n => x+nx+1 just throwing away terms in the expansion. So if a^n=b^n+1 or b^n+2, then n=1 which we assumed it wasn't, thus we have finished the proof, and nowhere did I invoke the rational numbers.
AlbertEinstein
#13
Oct9-06, 06:35 AM
P: 113
No, I didn't understand the assumption of a and b being coprime.But I understood that if they were not coprime then let a=x*a' and b=x*b' , then we can take x^n as common and then a'^n and b'^n will be coprime. Is this the reasoning behind the assumption? Please correct me.

>>Prove that if we can find an example, we can find an example with a,b coprime

well how do I prove this?
AlbertEinstein
#14
Oct9-06, 06:47 AM
P: 113
>>since a and b are coprime a^n-b^n equals 1 or 2

How?

>>(x+1)^n => x+nx+1 just throwing away terms in the expansion. So if a^n=b^n+1 or b^n+2, then n=1 which we assumed it wasn't

I am not able to follow.
Please Matt will you write the whole proof with rather more details.
matt grime
#15
Oct9-06, 06:51 AM
Sci Advisor
HW Helper
P: 9,398
Quote Quote by AlbertEinstein
No, I didn't understand the assumption of a and b being coprime.But I understood that if they were not coprime then let a=x*a' and b=x*b' , then we can take x^n as common and then a'^n and b'^n will be coprime. Is this the reasoning behind the assumption? Please correct me.

>>Prove that if we can find an example, we can find an example with a,b coprime

well how do I prove this?
You just did.
matt grime
#16
Oct9-06, 06:55 AM
Sci Advisor
HW Helper
P: 9,398
Quote Quote by AlbertEinstein
>>since a and b are coprime a^n-b^n equals 1 or 2

How?

because you know a^n-b^n divides both 2a^n and 2b^n, and a and b are coprime. The definition of highest common factor hcf(x,y) is that it divides x and y and evey other comon divisor of x and y divides it. Thus a^n-b^n divides the highest common factor of 2a^n and 2b^n which is 2.


>>(x+1)^n => x+nx+1 just throwing away terms in the expansion. So if a^n=b^n+1 or b^n+2, then n=1 which we assumed it wasn't

I am not able to follow.
Please Matt will you write the whole proof with rather more details.
what don't you follow? The next n'th power after x^n, which is (x+1)^n is at least 3 more than x^n if n=>2?

I used:

1. binomial expansion
2. subtraction of some terms

that is all.
AlbertEinstein
#17
Oct9-06, 11:06 AM
P: 113
Ok What I understood I will reproduce.Please look for any flaw.

Without the loss of generality we can suppose that (a,b) =1. Obviously,
[tex] a^n-b^n =/=1[/tex]

let us assume that [tex](a^n-b^n)|(a^n+b^n)[/tex]
Then [tex](a^n-b^n , a^n+b^n) = a^n-b^n[/tex]
But since (x,y) = (x,x+y) = (x,x-y) we have,
[tex] ((a^n-b^n),(a^n+b^n))=((a^n-b^n),2 a^n)=((a^n-b^n),2 b^n)=a^n-b^n[/tex]
Therefore [tex]a^n-b^n[/tex] must divide both 2a^n and 2b^n.
Hence [tex]a^n = 1+b^n or 2+b^n[/tex]
The first one contradicts our initial assumption and the second one contradicts the statement that the next n'th power after x^n, which is (x+1)^n is at least 3 more than x^n if n=>2, which is clear from binomial expansion.
These contradictions establish the given theorem.


If this is correct then please give some hints about the first question.
Thanks
JItendra
matt grime
#18
Oct9-06, 11:10 AM
Sci Advisor
HW Helper
P: 9,398
I am always troubled when people write out a proof and then say 'is this correct?' If you have to ask that then you don't understand the proof. (Or perhaps they don't understand whay it proves what they want it to prove.) So what part of that do no you not understand?


Register to reply

Related Discussions
Divisibility of n by 6 Linear & Abstract Algebra 10
Divisibility and p's and q's Precalculus Mathematics Homework 6
There exists or not exists a natural number Fun, Photos & Games 9
What is the remainder when 23 raised to 98 is divided by 98? Calculus & Beyond Homework 1
Divisibility Questions Calculus & Beyond Homework 5