Question

show that one and only one out of n,n+2,n+4 is divisible by 3.

Answer 1

Are you familiar with modular arithmetic?

Answer 2

no

Answer 3

hm...have you tried anything yet? any ideas on how you might show only one of those numbers can be a multiple of 3?

Answer 4

ya we have to do this by euclid's algorithm

Answer 5

Thats an interesting approach. The Euclidean Algorithm helps you find the gcd of 2 numbers. Im not sure how to apply that directly to this problem though =/.

Answer 6

anyways thks

Answer 7

One way to do this problem is to note that if you had two multiples of 3 (or multiples of any number for that matter), then when you subtract them, you still have a multiple of 3:\[3m-3n=3(m-n)\]You could use this to get a contradiction.

Answer 8

If n+2 and n were both multiples of 3, then (n+2)-n should also be a multiple of 3. But...

Answer 9

if n is even,
2k, 2k+2, 2k+4
2k, 2(k+1), 2(k+2)
only one of k,k+1 and k+2 must be divisible by 3.

if n is odd,
2k+1, 2k+3, 2k+5
2k+1, 2(k+1)+1, 2(k+2)+1
only one of 2k+1, 2(k+1)+1 and 2(k+2)+1 must be divisible by 3.

Answer 10

n = 3q + r (euclid's division lemma)
n is divisible by 3 only when r = 3k

now, for n, n+2, n+4
if we assume one is divisible by 3, others are not divisible by 3 because, they are away by 2 units from r.

Answer 11

how to write the working?

Answer 12

here goes :
As per Euclid's Division Lemma,
Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.

a = bq + r

since any number of the form 3k is divisible by 3 ( k is an integer)
a = 3q + r is divisible by 3 only when r is 0

n, n+2, n+4 are two units away from each other.
We can represent any one of these as "a = 3q + r" , (r=0), rest of the two wont satisfy the same because n+2 & n+4 are 2k distance away from each other.

Answer 13

Simply add the three numbers..
n + n + 2 + n + 4

You will get : 3n + 6
Taking 3 as common,
3(n + 2)

this value is divisible by 3 for all values of n because 3 is in multiplication...

Answer 14

suppose n the number divisible by 3, then we have to show n+2 and n+4 will not be divisible by 3:
so n=3p1, where p1 a natural number . by euclid's algorithm, we have:
n+2=3x1+2 <since 3 divides n
3=2x1+1
2=1x2
so the gcd of n+2 and 3 is 1, so that 3 cannot divide n+2
n+4=(n+3)+1=3(p1+1)+1< since 3 divides n and ofcourse 3
3=1x3
gcd of n+2 and three is 1 again, so that 3 cannot divide n+2
hence if 3 divides n, it may not divide the others.

Now suppose 3 divides n+2 so that n+2=3p2, where p2 is a natural number then:
since n+2/3 will give remainder 0, n+1/3 will give remainder 2, then n/3 will give remainder of 1 and then do euclid's algorithm:
n=3p3+1
3=1x3
gcd of n and 3 is 1 so that 3 doesn't divide n
n+4=(n+3)+1=3(p2+1)+1
3=1x3
so gcd of n+4 and 3 is 1 so that 3 doesn't divide n+4
now we see that if 3 divides n+2, it will not divide the others.

And now we suppose 3 divides n+4, so that n+4=3p4, where p4 is a natural number then:
since n+4/3 gives remainder 0, n+3/3 gives rem. 2, n+2/3 gives rem. 1, n+1/3 gives rem. 0, n/3 gives rem. 2, so
n=3p5+2
3=2x1+1
2=1x2
gcd of n and 3 is 1 so that 3 doesn't divide n
n+2=3p6+1
3=1x3
gcd of n+2 and 3 is 1, so that 3 doesn't divide n+2.
at last we see that if 3 divides n+4 it will not divide the others.

So if 3 divides one of the numbers n,n+2,n+4, it will not divide the others.
notice that we could've still proven it without EA, but since you are required to, i've considered it