Question

HELP NEEDED:
If X = {8^n - 7n - 1|n ∈ N} and Y = {49(n-1)|n ∈ N},
then prove that X ⊆ Y.
Do we just have to Plug-in values for n or is there any alternative method?

Answer 1

@satellite73
@experimentX

Answer 2

Anyone? :|

Answer 3

lets see what we can do
somehow it must be true that if \(z=8^n - 7n - 1\) then \(z\) can be written as \(49(n-1)\)

Answer 4

Yeah

Answer 5

Can we do this By combination?

Answer 6

i don't know i am not that fast
my first thought was to factor \(8^n-1\) as the difference of two cubes

Answer 7

but now i think @experimentX has a better idea

Answer 8

lol ... no i don't I just came back :) after walk

Answer 9

heheh

Answer 10

Thanks @satellite73 !
I'll go through it once more and see!

Answer 11

maybe it would be easier by induction?

Answer 12

Principal Of Mathematical Induction?
I'll try THAT out!
Thanks!! :D

Answer 13

i will bet induction and some algebra will work
certainly true for \(n=1\)

Answer 14

show that
\[ 1 + 8 + ... +8^{n-1} = n \mod 7 \]

Answer 15

It DOES work with 1 and 2

Answer 16

for all n , 8^n = 1 mod 7
add it n times from 0 to n-1

Answer 17

Certainly works by induction: you can prove that \(8^n - 7n - 1\) is divisible by 49 for any \(n\). But experimentX's method looks neater...

Answer 18

k but how to prove that \(8^k\equiv 1 (7)\)?

Answer 19

and you are not allowed to say "by induction!"

Answer 20

ab mod c = ((a mod c)(b mod c)) mod c

Answer 21

yeah, but what about the \(k\)? ok i am being silly

Answer 22

hmm ... (abcd ... k) mod c = (a mod c)(b mod c) ... (k mod c) mod c
since all terms are 8 and the remainder is 1, the remainder is also 1. I think this can be done better via euler totient function. I am little out of touch on this.

Answer 23

@satellite73 I guess your point is that 8^n = 1 mod 7 implicitly requires induction (e.g. ab mod c = ((a mod c)(b mod c)) mod c applied "repeatedly") to be proved formally? ;-)

Answer 24

Thanks for your help. I got it by using Principal of Mathematical Induction.