Congruence with algebraic exponents
up vote
1
down vote
favorite
I have done a number of congruence questions but then I encountered this question:
$7^{x+2} ≡ 5(mod 29)$
How do you go around solving this? I thought of splitting the powers to $7^x$ and $7^2$ but then I got stuck trying to evaluate it...
number-theory modular-arithmetic
asked Nov 16 at 4:12
Caleb Gicheru
82
add a comment |
up vote
1
down vote
favorite
I have done a number of congruence questions but then I encountered this question:
$7^{x+2} ≡ 5(mod 29)$
How do you go around solving this? I thought of splitting the powers to $7^x$ and $7^2$ but then I got stuck trying to evaluate it...
number-theory modular-arithmetic
asked Nov 16 at 4:12
Caleb Gicheru
82
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have done a number of congruence questions but then I encountered this question:
$7^{x+2} ≡ 5(mod 29)$
How do you go around solving this? I thought of splitting the powers to $7^x$ and $7^2$ but then I got stuck trying to evaluate it...
number-theory modular-arithmetic
asked Nov 16 at 4:12
Caleb Gicheru
82
I have done a number of congruence questions but then I encountered this question:
$7^{x+2} ≡ 5(mod 29)$
How do you go around solving this? I thought of splitting the powers to $7^x$ and $7^2$ but then I got stuck trying to evaluate it...
number-theory modular-arithmetic
number-theory modular-arithmetic
asked Nov 16 at 4:12
Caleb Gicheru
82
asked Nov 16 at 4:12
Caleb Gicheru
82
asked Nov 16 at 4:12
Caleb Gicheru
82
asked Nov 16 at 4:12
Caleb Gicheru
82
asked Nov 16 at 4:12
Caleb Gicheru
82
82
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Evaluating powers of $7$, mod $29$, we get
begin{align*}
7^0 equiv 1;(text{mod};29)\[4pt]
7^1 equiv 7;(text{mod};29)\[4pt]
7^2 equiv 20;(text{mod};29)\[4pt]
7^3 equiv 24;(text{mod};29)\[4pt]
7^4 equiv 23;(text{mod};29)\[4pt]
7^5 equiv 16;(text{mod};29)\[4pt]
7^6 equiv 25;(text{mod};29)\[4pt]
7^7 equiv 1;(text{mod};29)\[4pt]
end{align*}
after which, the cycle repeats forever.
It follows that no power of $7$ is congruent to $5$, mod $29$.
answered Nov 16 at 4:33
quasi
35.9k22562
add a comment |
up vote
1
down vote
$2$ can be proved to be a primitive root
$2^6equiv6,2^7equiv12,2^8equiv-5,2^{14}equiv12^2equiv-1pmod{29}$
$5=(-5)(-1)equiv2^{8+14}$
$7equiv29+7equiv6^2equiv(2^6)^2$
Using discrete logarithm, $(x+2)12equiv22pmod{phi(29)}$
answered Nov 16 at 4:34
lab bhattacharjee
220k15154271
math.stackexchange.com/questions/741832/…
– lab bhattacharjee
Nov 16 at 5:06
i.e. $bmod 29!: 5$ is not a $4$th power $(4nmid 22)$ but $7$ is $(4mid 12)$ so $7^n$ is too, thus $5notequiv 7^n. $ Said equivalently $,7^7equiv 1,$ but $5^7notequiv 1 $
– Bill Dubuque
Nov 16 at 17:57
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Evaluating powers of $7$, mod $29$, we get
begin{align*}
7^0 equiv 1;(text{mod};29)\[4pt]
7^1 equiv 7;(text{mod};29)\[4pt]
7^2 equiv 20;(text{mod};29)\[4pt]
7^3 equiv 24;(text{mod};29)\[4pt]
7^4 equiv 23;(text{mod};29)\[4pt]
7^5 equiv 16;(text{mod};29)\[4pt]
7^6 equiv 25;(text{mod};29)\[4pt]
7^7 equiv 1;(text{mod};29)\[4pt]
end{align*}
after which, the cycle repeats forever.
It follows that no power of $7$ is congruent to $5$, mod $29$.
answered Nov 16 at 4:33
quasi
35.9k22562
add a comment |
up vote
1
down vote
accepted
Evaluating powers of $7$, mod $29$, we get
begin{align*}
7^0 equiv 1;(text{mod};29)\[4pt]
7^1 equiv 7;(text{mod};29)\[4pt]
7^2 equiv 20;(text{mod};29)\[4pt]
7^3 equiv 24;(text{mod};29)\[4pt]
7^4 equiv 23;(text{mod};29)\[4pt]
7^5 equiv 16;(text{mod};29)\[4pt]
7^6 equiv 25;(text{mod};29)\[4pt]
7^7 equiv 1;(text{mod};29)\[4pt]
end{align*}
after which, the cycle repeats forever.
It follows that no power of $7$ is congruent to $5$, mod $29$.
answered Nov 16 at 4:33
quasi
35.9k22562
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Evaluating powers of $7$, mod $29$, we get
begin{align*}
7^0 equiv 1;(text{mod};29)\[4pt]
7^1 equiv 7;(text{mod};29)\[4pt]
7^2 equiv 20;(text{mod};29)\[4pt]
7^3 equiv 24;(text{mod};29)\[4pt]
7^4 equiv 23;(text{mod};29)\[4pt]
7^5 equiv 16;(text{mod};29)\[4pt]
7^6 equiv 25;(text{mod};29)\[4pt]
7^7 equiv 1;(text{mod};29)\[4pt]
end{align*}
after which, the cycle repeats forever.
It follows that no power of $7$ is congruent to $5$, mod $29$.
answered Nov 16 at 4:33
quasi
35.9k22562
Evaluating powers of $7$, mod $29$, we get
begin{align*}
7^0 equiv 1;(text{mod};29)\[4pt]
7^1 equiv 7;(text{mod};29)\[4pt]
7^2 equiv 20;(text{mod};29)\[4pt]
7^3 equiv 24;(text{mod};29)\[4pt]
7^4 equiv 23;(text{mod};29)\[4pt]
7^5 equiv 16;(text{mod};29)\[4pt]
7^6 equiv 25;(text{mod};29)\[4pt]
7^7 equiv 1;(text{mod};29)\[4pt]
end{align*}
after which, the cycle repeats forever.
It follows that no power of $7$ is congruent to $5$, mod $29$.
answered Nov 16 at 4:33
quasi
35.9k22562
answered Nov 16 at 4:33
quasi
35.9k22562
answered Nov 16 at 4:33
quasi
35.9k22562
answered Nov 16 at 4:33
quasi
35.9k22562
35.9k22562
add a comment |
add a comment |
up vote
1
down vote
$2$ can be proved to be a primitive root
$2^6equiv6,2^7equiv12,2^8equiv-5,2^{14}equiv12^2equiv-1pmod{29}$
$5=(-5)(-1)equiv2^{8+14}$
$7equiv29+7equiv6^2equiv(2^6)^2$
Using discrete logarithm, $(x+2)12equiv22pmod{phi(29)}$
answered Nov 16 at 4:34
lab bhattacharjee
220k15154271
math.stackexchange.com/questions/741832/…
– lab bhattacharjee
Nov 16 at 5:06
i.e. $bmod 29!: 5$ is not a $4$th power $(4nmid 22)$ but $7$ is $(4mid 12)$ so $7^n$ is too, thus $5notequiv 7^n. $ Said equivalently $,7^7equiv 1,$ but $5^7notequiv 1 $
– Bill Dubuque
Nov 16 at 17:57
add a comment |
up vote
1
down vote
$2$ can be proved to be a primitive root
$2^6equiv6,2^7equiv12,2^8equiv-5,2^{14}equiv12^2equiv-1pmod{29}$
$5=(-5)(-1)equiv2^{8+14}$
$7equiv29+7equiv6^2equiv(2^6)^2$
Using discrete logarithm, $(x+2)12equiv22pmod{phi(29)}$
answered Nov 16 at 4:34
lab bhattacharjee
220k15154271
math.stackexchange.com/questions/741832/…
– lab bhattacharjee
Nov 16 at 5:06
i.e. $bmod 29!: 5$ is not a $4$th power $(4nmid 22)$ but $7$ is $(4mid 12)$ so $7^n$ is too, thus $5notequiv 7^n. $ Said equivalently $,7^7equiv 1,$ but $5^7notequiv 1 $
– Bill Dubuque
Nov 16 at 17:57
add a comment |
up vote
1
down vote
up vote
1
down vote
$2$ can be proved to be a primitive root
$2^6equiv6,2^7equiv12,2^8equiv-5,2^{14}equiv12^2equiv-1pmod{29}$
$5=(-5)(-1)equiv2^{8+14}$
$7equiv29+7equiv6^2equiv(2^6)^2$
Using discrete logarithm, $(x+2)12equiv22pmod{phi(29)}$
answered Nov 16 at 4:34
lab bhattacharjee
220k15154271
$2$ can be proved to be a primitive root
$2^6equiv6,2^7equiv12,2^8equiv-5,2^{14}equiv12^2equiv-1pmod{29}$
$5=(-5)(-1)equiv2^{8+14}$
$7equiv29+7equiv6^2equiv(2^6)^2$
Using discrete logarithm, $(x+2)12equiv22pmod{phi(29)}$
answered Nov 16 at 4:34
lab bhattacharjee
220k15154271
answered Nov 16 at 4:34
lab bhattacharjee
220k15154271
answered Nov 16 at 4:34
lab bhattacharjee
220k15154271
answered Nov 16 at 4:34
lab bhattacharjee
220k15154271
220k15154271
math.stackexchange.com/questions/741832/…
– lab bhattacharjee
Nov 16 at 5:06
i.e. $bmod 29!: 5$ is not a $4$th power $(4nmid 22)$ but $7$ is $(4mid 12)$ so $7^n$ is too, thus $5notequiv 7^n. $ Said equivalently $,7^7equiv 1,$ but $5^7notequiv 1 $
– Bill Dubuque
Nov 16 at 17:57
add a comment |
math.stackexchange.com/questions/741832/…
– lab bhattacharjee
Nov 16 at 5:06
i.e. $bmod 29!: 5$ is not a $4$th power $(4nmid 22)$ but $7$ is $(4mid 12)$ so $7^n$ is too, thus $5notequiv 7^n. $ Said equivalently $,7^7equiv 1,$ but $5^7notequiv 1 $
– Bill Dubuque
Nov 16 at 17:57
math.stackexchange.com/questions/741832/…
– lab bhattacharjee
Nov 16 at 5:06
math.stackexchange.com/questions/741832/…
– lab bhattacharjee
Nov 16 at 5:06
i.e. $bmod 29!: 5$ is not a $4$th power $(4nmid 22)$ but $7$ is $(4mid 12)$ so $7^n$ is too, thus $5notequiv 7^n. $ Said equivalently $,7^7equiv 1,$ but $5^7notequiv 1 $
– Bill Dubuque
Nov 16 at 17:57
i.e. $bmod 29!: 5$ is not a $4$th power $(4nmid 22)$ but $7$ is $(4mid 12)$ so $7^n$ is too, thus $5notequiv 7^n. $ Said equivalently $,7^7equiv 1,$ but $5^7notequiv 1 $
– Bill Dubuque
Nov 16 at 17:57
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3000707%2fcongruence-with-algebraic-exponents%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
