I'm starting to solve some problems of congruence and integer division, so the exercise is quite simple but I'm not sure I'm on the right track. I need to prove that the following is true for all n∈N:
9 | 7⋅52n+24n+1
This is what I have so far:
7⋅52n+24n+1≡0 (9)
So I try to see what each side of the sum is congruent to: 7≡−2 (9) and 52n≡42n(9), hence: 7⋅52n≡−2⋅42n (9) and the left side is also congruent to: −2⋅42n≡7n⋅−2 (9) which leaves me with:
7⋅52n≡7n⋅−2 (9)
As for the other side:
24n+1≡74n⋅ 2 (9)
Finally combining them:
7⋅52n+24n+1≡7n⋅(−2)+74n⋅ 2 (9)
Am I right so far? Any hint on how to continue?
Thanks!
Answer
Alternative proof by induction.
First, show that this is true for n=0:
7⋅52⋅0+24⋅0+1=9
Second, assume that this is true for n:
7⋅52n+24n+1=9k
Third, prove that this is true for n+1:
7⋅52(n+1)+24(n+1)+1=
16⋅(7⋅52n+24n+1)+63⋅52n=
16⋅9k+63⋅52n=
9⋅(16k+7⋅52n)
Please note that the assumption is used only in the part marked red.
No comments:
Post a Comment