Number Theory: 13 | 3^(n+2) + 4^(2n+1)

[Jamers328]

Hello! I have a couple of problems that I am getting stuck at a certain step on.

What is the best way to type out exponents though? There are a lot of exponents in these problems? I'll edit the problems after someone replies to that.


1. 13 | 3^(n+2) + 4^(2n+1)

=3^n x 3^2 + (4^2)^n x 4^1 = 3^n x 9 + 16 x 4 = 3^n x 9 + 3^n x 4 =

The equal signs really should be congruence signs. I thought that after working through the problem there would be a 3^n and -3^n that I could cancel... but there's not. The second problem I need help with is just like this one... it ends up with a 6^n and another 6^n... What am I doing wrong?

Thanks so much...

 

[stapel]

Re: Number Theory

What is the best way to type out exponents though?

The "carat" symbol is fine.

1. 13 | 3^(n+2) + 4^(2n+1)

What are you supposed to be doing with this? I don't see any instructions or an actual question to answer...?

I thought that after working through the problem there would be a 3^n and -3^n that I could cancel... but there's not.

Why? How does this relate to whatever you're doing in this exercise?

The second problem I need help with is just like this one... it ends up with a 6^n and another 6^n... What am I doing wrong?

Without knowing what the exercise was, what the instructions were, what you did, or what the answer was supposed to be, I'm afraid there is no way to answer your question. Sorry! :shock:

Eliz.

 

[pka]

Do this by induction.
If N=1, then 13 divides 91. So it is true for N=1.
Suppose that it is true for N=K; i.e. \(\displaystyle 13\left| {\left( {3^{K + 2} + 4^{2K + 1} } \right)} \right.\)

Look at
\(\displaystyle \begin{array}{rcl}
3^{\left( {K + 1} \right) + 2} + 4^{2\left( {K + 1} \right) + 1} & = & 3^{K + 3} + 4^{2K + 3} \\
& = & 3^{K + 3} + 3\left( {4^{2k + 1} } \right) - 3\left( {4^{2k + 1} } \right) + 4^{2K + 3} \\
& = & 3\left[ {\underbrace {3^{K + 2} + 4^{2k + 1} }_{13|\left[ {3^{K + 2} + 4^{2k + 1} } \right]}} \right] - 4^{2k + 1} \left[ {\underbrace {3 - 4^2 }_{ - 13}} \right] \\
\end{array}\)

True for N=K+1.

 

[Jamers328]

Re: Number Theory

1. 13 | 3^(n+2) + 4^(2n+1)

What are you supposed to be doing with this? I don't see any instructions or an actual question to answer...?

I'm sorry I wasn't more specific. Here, maybe this will help...

For n >= 1, use congruence theory to establish each of the following divisibility statements:

b. 13 | 3^(n+3) + 4^(2n+1)
d. 43 | 6^(n+2) + 7^(2n+1)

So we are supposed to be using congruences.. that's why I said my = sign from my work was supposed to be a congruence sign (with the three bars).

Did this help at all? I'm sorry.

 

[stapel]

I think you can fake a "congruence" symbol by underlining the "equals" sign, like this:

. . . . .3ⁿ⁺³ + 4²ⁿ⁺¹ = 0 (mod 13)

Is that the sort of thing you mean...? If so, then note that you can do it in LaTeX, too:

. . . . .\(\displaystyle \L 3^{n\, +\, 3}\, +\, 4^{2n\, +\, 1}\, \equiv \, 0\, (mod 13)\)



Eliz.

 

[Jamers328]

. . . . .\(\displaystyle \L 3^{n\, +\, 3}\, +\, 4^{2n\, +\, 1}\, \equiv \, 0\, (mod 13)\)

That looks awesome.

How did you get 0 though???

 

[pka]

Jamers328, Why do you think that this is a congruence problem?
As far as I can see, this is a straightforward induction problem.
You list this as a Number Theory problem. What textbook are you using?

 

[Jamers328]

my textbook is called Elementary Number Theory by David M Burton.

it is for my number theory class, and the book says to use congruence theory to solve it.

 

[stapel]

How did you get 0 though???

If a number n divides evenly into another number, isn't it equal to 0, mod n? Isn't that the definition of "modulo" and "dividing in evenly"?

Perhaps I'm not understanding your question...?

Eliz.

 

[Jamers328]

If a number n divides evenly into another number, isn't it equal to 0, mod n? Isn't that the definition of "modulo" and "dividing in evenly"?

Yes, but how do you know that that number divides evenly with 13? I'm not saying 0 is wrong, you are probably right, but I can't work out the problem to get there. Did you understand any of the work I put in my first post?

 

[stapel]

Yes, but how do you know that that number divides evenly with 13?

Wasn't that the original problem statement, that you're supposed to prove division by 13...?

Eliz.

 

[Jamers328]

Wasn't that the original problem statement, that you're supposed to prove division by 13...?

yeah, but I have to show work. I tried showing work but I couldn't get it out to be the right answer. I know the answer and how to write it, I am just stuck on that step I showed in my first post. I'm so sorry if I am being confusing. Thank you so much for talking to me about this!

 

[Deleted member 4993]

Look at pka's post - very carefully.

He has proved it for you - "congruence" symbol not withstanding.

 

[stapel]

Wasn't that the original problem statement, that you're supposed to prove division by 13...?

yeah, but I have to show work.

So, use what pka gave you, and show the work. I was just answering your question about formatting.

Eliz.

 

[pka]

my textbook is called Elementary Number Theory by David M Burton. It is for my number theory class, and the book says to use congruence theory to solve it.

I apologize for creating any confusion here. Once I saw the above answer, I realized that indeed he/she does require a proof by congruence. But I was already working on something else and did not stop to think about this. (The truth is that I do not care much for number theory.)

But, I think that the other lesson here is this: the question could have been put more clearly. It should have been clearly stated with details about what should be done.

In any case all these proofs require a cute trick.
Realize this: \(\displaystyle 9 \equiv - 4\;\bmod (13)\quad \& \quad 16 \equiv 3\;\bmod (13)\)
\(\displaystyle 3^{n + 2} + 4^{2n + 1} = \left( 9 \right)3^n + 4\left( {16} \right)^n\)
\(\displaystyle \left( 9 \right)3^n + 4\left( {16} \right)^n \equiv \left( { - 4} \right)3^n + 4\left( {3^n } \right) \equiv 0\;\bmod (13)\).

 

[Jamers328]

my textbook is called Elementary Number Theory by David M Burton. It is for my number theory class, and the book says to use congruence theory to solve it.

I apologize for creating any confusion here. Once I saw the above answer, I realized that indeed he/she does require a proof by congruence. But I was already working on something else and did not stop to think about this. (The truth is that I do not care much for number theory.)

But, I think that the other lesson here is this: the question could have been put more clearly. It should have been clearly stated with details about what should be done.

In any case all these proofs require a cute trick.
Realize this: \(\displaystyle 9 \equiv - 4\;\bmod (13)\quad \& \quad 16 \equiv 3\;\bmod (13)\)
\(\displaystyle 3^{n + 2} + 4^{2n + 1} = \left( 9 \right)3^n + 4\left( {16} \right)^n\)
\(\displaystyle \left( 9 \right)3^n + 4\left( {16} \right)^n \equiv \left( { - 4} \right)3^n + 4\left( {3^n } \right) \equiv 0\;\bmod (13)\).

Thank you very much! All I needed was that -4... I wasn't thinking hard enough. Thank you for your help.

Thank you too, Eliz.

I apologize for not being more clear with the directions of the problem. Next time, I will be much more clear. Sorry.

 

[soroban]

Hello, Jamers328!

1. Prove that: \(\displaystyle \: 13\,|\,3^{n+2}\,+\,4^{2n+1}\)

You were off to a great start . . . just another step or two . . .

\(\displaystyle 3^{n+2}\,+\,4^{2n+1} \;=\;3^n\cdot3^2\,+\,4^{2n}\cdot4^1\)

. . . . . . . . . . \(\displaystyle =\;9\cdot3^n \,+\,4\cdot16^n\)

. . . . . . . . . . \(\displaystyle \equiv\;9\cdot3^n \,+\,4\cdot3^n\:\pmod{13}\)

. . . . . . . . . . \(\displaystyle \equiv\;(9\,+\,4)\cdot 3^n\;\pmod{13}\)

. . . . . . . . . . \(\displaystyle \equiv \;13\cdot3^n\;\pmod{13}\)

. . . . . . . . . . \(\displaystyle \equiv\;0\;\pmod{13}\)


Therefore: \(\displaystyle \,3^{n+2}\,+\,4^{2n+1}\) is a multiple of 13.