Mixing
For any $a in mathbb{N}$, $4^a equiv (3a+1) mod 9$ [duplicate]
$begingroup$
This question already has an answer here:
Proving that $7^n(3n+1)-1$ is divisible by 9
6 answers
For any $a in mathbb{N}$, $4^a equiv (3a+1) mod 9$. How do I prove this?
I have attempted to do so by induction(which I think should be sufficient).
For the base case: $4^0 = 1 equiv (3(0)+1) mod 9$.
I have tried assuming the inductive hypothesis $4^a equiv (3a+1) mod 9$ to try and get the result to be true for say $a+1$ but I can't get past that point and don't know whether this is the correct route. Any help would be appreciated.
elementary-number-theory proof-verification proof-writing modular-arithmetic induction
asked Jan 25 at 5:36
YFPYFP
537
$endgroup$
marked as duplicate by Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 25 at 15:58
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Proving that $7^n(3n+1)-1$ is divisible by 9
6 answers
For any $a in mathbb{N}$, $4^a equiv (3a+1) mod 9$. How do I prove this?
I have attempted to do so by induction(which I think should be sufficient).
For the base case: $4^0 = 1 equiv (3(0)+1) mod 9$.
I have tried assuming the inductive hypothesis $4^a equiv (3a+1) mod 9$ to try and get the result to be true for say $a+1$ but I can't get past that point and don't know whether this is the correct route. Any help would be appreciated.
elementary-number-theory proof-verification proof-writing modular-arithmetic induction
asked Jan 25 at 5:36
YFPYFP
537
$endgroup$
marked as duplicate by Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 25 at 15:58
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
by induction the problem is trivial , just from the inductive stage multiply both sides by 4 and rearrange right hand side you will get an extra 9a term which off course divisible by 9
$endgroup$
– Bijayan Ray
Jan 25 at 5:43
$begingroup$
@BijayanRay Thanks for your reply. I have already tried that and there is a but there is a remainder 3 there as well.
$endgroup$
– YFP
Jan 25 at 5:50
$begingroup$
how you are getting 12a +4=9a+3(a+1)+1
$endgroup$
– Bijayan Ray
Jan 25 at 5:51
$begingroup$
Oh my bad, I just realized! Sorry about that.
$endgroup$
– YFP
Jan 25 at 5:55
add a comment |
$begingroup$
This question already has an answer here:
Proving that $7^n(3n+1)-1$ is divisible by 9
6 answers
For any $a in mathbb{N}$, $4^a equiv (3a+1) mod 9$. How do I prove this?
I have attempted to do so by induction(which I think should be sufficient).
For the base case: $4^0 = 1 equiv (3(0)+1) mod 9$.
I have tried assuming the inductive hypothesis $4^a equiv (3a+1) mod 9$ to try and get the result to be true for say $a+1$ but I can't get past that point and don't know whether this is the correct route. Any help would be appreciated.
elementary-number-theory proof-verification proof-writing modular-arithmetic induction
asked Jan 25 at 5:36
YFPYFP
537
$endgroup$
This question already has an answer here:
Proving that $7^n(3n+1)-1$ is divisible by 9
6 answers
For any $a in mathbb{N}$, $4^a equiv (3a+1) mod 9$. How do I prove this?
I have attempted to do so by induction(which I think should be sufficient).
For the base case: $4^0 = 1 equiv (3(0)+1) mod 9$.
I have tried assuming the inductive hypothesis $4^a equiv (3a+1) mod 9$ to try and get the result to be true for say $a+1$ but I can't get past that point and don't know whether this is the correct route. Any help would be appreciated.
This question already has an answer here:
Proving that $7^n(3n+1)-1$ is divisible by 9
6 answers
elementary-number-theory proof-verification proof-writing modular-arithmetic induction
elementary-number-theory proof-verification proof-writing modular-arithmetic induction
asked Jan 25 at 5:36
YFPYFP
537
asked Jan 25 at 5:36
YFPYFP
537
asked Jan 25 at 5:36
YFPYFP
537
asked Jan 25 at 5:36
YFPYFP
537
asked Jan 25 at 5:36
YFPYFP
537
537
marked as duplicate by Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 25 at 15:58
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 25 at 15:58
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
by induction the problem is trivial , just from the inductive stage multiply both sides by 4 and rearrange right hand side you will get an extra 9a term which off course divisible by 9
$endgroup$
– Bijayan Ray
Jan 25 at 5:43
$begingroup$
@BijayanRay Thanks for your reply. I have already tried that and there is a but there is a remainder 3 there as well.
$endgroup$
– YFP
Jan 25 at 5:50
$begingroup$
how you are getting 12a +4=9a+3(a+1)+1
$endgroup$
– Bijayan Ray
Jan 25 at 5:51
$begingroup$
Oh my bad, I just realized! Sorry about that.
$endgroup$
– YFP
Jan 25 at 5:55
add a comment |
1
$begingroup$
by induction the problem is trivial , just from the inductive stage multiply both sides by 4 and rearrange right hand side you will get an extra 9a term which off course divisible by 9
$endgroup$
– Bijayan Ray
Jan 25 at 5:43
$begingroup$
@BijayanRay Thanks for your reply. I have already tried that and there is a but there is a remainder 3 there as well.
$endgroup$
– YFP
Jan 25 at 5:50
$begingroup$
how you are getting 12a +4=9a+3(a+1)+1
$endgroup$
– Bijayan Ray
Jan 25 at 5:51
$begingroup$
Oh my bad, I just realized! Sorry about that.
$endgroup$
– YFP
Jan 25 at 5:55
1
1
$begingroup$
by induction the problem is trivial , just from the inductive stage multiply both sides by 4 and rearrange right hand side you will get an extra 9a term which off course divisible by 9
$endgroup$
– Bijayan Ray
Jan 25 at 5:43
$begingroup$
by induction the problem is trivial , just from the inductive stage multiply both sides by 4 and rearrange right hand side you will get an extra 9a term which off course divisible by 9
$endgroup$
– Bijayan Ray
Jan 25 at 5:43
$begingroup$
@BijayanRay Thanks for your reply. I have already tried that and there is a but there is a remainder 3 there as well.
$endgroup$
– YFP
Jan 25 at 5:50
$begingroup$
@BijayanRay Thanks for your reply. I have already tried that and there is a but there is a remainder 3 there as well.
$endgroup$
– YFP
Jan 25 at 5:50
$begingroup$
how you are getting 12a +4=9a+3(a+1)+1
$endgroup$
– Bijayan Ray
Jan 25 at 5:51
$begingroup$
how you are getting 12a +4=9a+3(a+1)+1
$endgroup$
– Bijayan Ray
Jan 25 at 5:51
$begingroup$
Oh my bad, I just realized! Sorry about that.
$endgroup$
– YFP
Jan 25 at 5:55
$begingroup$
Oh my bad, I just realized! Sorry about that.
$endgroup$
– YFP
Jan 25 at 5:55
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint:
Note that
$$4^a = (3+1)^a = 1+ binom{a}{1}3 + binom{a}{2}3^2 + cdots +3^a=1+3a +9 left(binom{a}{2}+ binom{a}{3}3+cdots + 3^{a-2} right)$$
If you insist on induction the induction step can be performed as follows:
begin{eqnarray*} 4^{a+1}
& equiv_9 & 4cdot 4^a \
& equiv_9 & (3+1)cdot (3a+1) \
& equiv_9 & 3cdot (3a+1) + 3a+1 \
& equiv_9 & 9a+3 + 3a+1 \
& equiv_9 & 3(a+1) +1 \
end{eqnarray*}
answered Jan 25 at 5:44
trancelocationtrancelocation
12.7k1827
$endgroup$
$begingroup$
A nice solution!
$endgroup$
– Bernard Hurley
Jan 25 at 6:10
$begingroup$
Just as easy (and more general) to inductively prove the first two terms of the Binomial Theorem, e.g. see here.
$endgroup$
– Bill Dubuque
Jan 25 at 16:00
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint:
Note that
$$4^a = (3+1)^a = 1+ binom{a}{1}3 + binom{a}{2}3^2 + cdots +3^a=1+3a +9 left(binom{a}{2}+ binom{a}{3}3+cdots + 3^{a-2} right)$$
If you insist on induction the induction step can be performed as follows:
begin{eqnarray*} 4^{a+1}
& equiv_9 & 4cdot 4^a \
& equiv_9 & (3+1)cdot (3a+1) \
& equiv_9 & 3cdot (3a+1) + 3a+1 \
& equiv_9 & 9a+3 + 3a+1 \
& equiv_9 & 3(a+1) +1 \
end{eqnarray*}
answered Jan 25 at 5:44
trancelocationtrancelocation
12.7k1827
$endgroup$
$begingroup$
A nice solution!
$endgroup$
– Bernard Hurley
Jan 25 at 6:10
$begingroup$
Just as easy (and more general) to inductively prove the first two terms of the Binomial Theorem, e.g. see here.
$endgroup$
– Bill Dubuque
Jan 25 at 16:00
add a comment |
$begingroup$
Hint:
Note that
$$4^a = (3+1)^a = 1+ binom{a}{1}3 + binom{a}{2}3^2 + cdots +3^a=1+3a +9 left(binom{a}{2}+ binom{a}{3}3+cdots + 3^{a-2} right)$$
If you insist on induction the induction step can be performed as follows:
begin{eqnarray*} 4^{a+1}
& equiv_9 & 4cdot 4^a \
& equiv_9 & (3+1)cdot (3a+1) \
& equiv_9 & 3cdot (3a+1) + 3a+1 \
& equiv_9 & 9a+3 + 3a+1 \
& equiv_9 & 3(a+1) +1 \
end{eqnarray*}
answered Jan 25 at 5:44
trancelocationtrancelocation
12.7k1827
$endgroup$
$begingroup$
A nice solution!
$endgroup$
– Bernard Hurley
Jan 25 at 6:10
$begingroup$
Just as easy (and more general) to inductively prove the first two terms of the Binomial Theorem, e.g. see here.
$endgroup$
– Bill Dubuque
Jan 25 at 16:00
add a comment |
$begingroup$
Hint:
Note that
$$4^a = (3+1)^a = 1+ binom{a}{1}3 + binom{a}{2}3^2 + cdots +3^a=1+3a +9 left(binom{a}{2}+ binom{a}{3}3+cdots + 3^{a-2} right)$$
If you insist on induction the induction step can be performed as follows:
begin{eqnarray*} 4^{a+1}
& equiv_9 & 4cdot 4^a \
& equiv_9 & (3+1)cdot (3a+1) \
& equiv_9 & 3cdot (3a+1) + 3a+1 \
& equiv_9 & 9a+3 + 3a+1 \
& equiv_9 & 3(a+1) +1 \
end{eqnarray*}
answered Jan 25 at 5:44
trancelocationtrancelocation
12.7k1827
$endgroup$
Hint:
Note that
$$4^a = (3+1)^a = 1+ binom{a}{1}3 + binom{a}{2}3^2 + cdots +3^a=1+3a +9 left(binom{a}{2}+ binom{a}{3}3+cdots + 3^{a-2} right)$$
If you insist on induction the induction step can be performed as follows:
begin{eqnarray*} 4^{a+1}
& equiv_9 & 4cdot 4^a \
& equiv_9 & (3+1)cdot (3a+1) \
& equiv_9 & 3cdot (3a+1) + 3a+1 \
& equiv_9 & 9a+3 + 3a+1 \
& equiv_9 & 3(a+1) +1 \
end{eqnarray*}
answered Jan 25 at 5:44
trancelocationtrancelocation
12.7k1827
edited Jan 25 at 7:33
answered Jan 25 at 5:44
trancelocationtrancelocation
12.7k1827
answered Jan 25 at 5:44
trancelocationtrancelocation
12.7k1827
answered Jan 25 at 5:44
trancelocationtrancelocation
12.7k1827
12.7k1827
$begingroup$
A nice solution!
$endgroup$
– Bernard Hurley
Jan 25 at 6:10
$begingroup$
Just as easy (and more general) to inductively prove the first two terms of the Binomial Theorem, e.g. see here.
$endgroup$
– Bill Dubuque
Jan 25 at 16:00
add a comment |
$begingroup$
A nice solution!
$endgroup$
– Bernard Hurley
Jan 25 at 6:10
$begingroup$
Just as easy (and more general) to inductively prove the first two terms of the Binomial Theorem, e.g. see here.
$endgroup$
– Bill Dubuque
Jan 25 at 16:00
$begingroup$
A nice solution!
$endgroup$
– Bernard Hurley
Jan 25 at 6:10
$begingroup$
A nice solution!
$endgroup$
– Bernard Hurley
Jan 25 at 6:10
$begingroup$
Just as easy (and more general) to inductively prove the first two terms of the Binomial Theorem, e.g. see here.
$endgroup$
– Bill Dubuque
Jan 25 at 16:00
$begingroup$
Just as easy (and more general) to inductively prove the first two terms of the Binomial Theorem, e.g. see here.
$endgroup$
– Bill Dubuque
Jan 25 at 16:00
add a comment |
1
$begingroup$
by induction the problem is trivial , just from the inductive stage multiply both sides by 4 and rearrange right hand side you will get an extra 9a term which off course divisible by 9
$endgroup$
– Bijayan Ray
Jan 25 at 5:43
$begingroup$
@BijayanRay Thanks for your reply. I have already tried that and there is a but there is a remainder 3 there as well.
$endgroup$
– YFP
Jan 25 at 5:50
$begingroup$
how you are getting 12a +4=9a+3(a+1)+1
$endgroup$
– Bijayan Ray
Jan 25 at 5:51
$begingroup$
Oh my bad, I just realized! Sorry about that.
$endgroup$
– YFP
Jan 25 at 5:55