Mixing
Applying Fermats Little Theorem to show $a^p equiv_p b^p $ implies $a equiv_p b $
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let $p$ be a prime number and $a$,$b$ be two positive integers.
Show that
beginequation
a^p equiv_p b^p implies a equiv_p b
endequation
I'm thinking the best way to show this relationship is using Fermat's Little Theorem two times?
Maybe this can be done simply using the properties of Modular arithmetics?
FLT states that if $p$ is a prime number, then for any integer $a$, the number $a^p-a$ is an integer multiple of $p$.
Expressed :
$a^p equiv_p a$
I'm not sure how to apply FLT in this case, any help would be much appreciated!
elementary-number-theory modular-arithmetic
edited Jul 31 at 21:29
amWhy
189k25219431
asked Jul 31 at 21:20
einar
1238
add a comment |Â
up vote
2
down vote
favorite
Let $p$ be a prime number and $a$,$b$ be two positive integers.
Show that
beginequation
a^p equiv_p b^p implies a equiv_p b
endequation
I'm thinking the best way to show this relationship is using Fermat's Little Theorem two times?
Maybe this can be done simply using the properties of Modular arithmetics?
FLT states that if $p$ is a prime number, then for any integer $a$, the number $a^p-a$ is an integer multiple of $p$.
Expressed :
$a^p equiv_p a$
I'm not sure how to apply FLT in this case, any help would be much appreciated!
elementary-number-theory modular-arithmetic
edited Jul 31 at 21:29
amWhy
189k25219431
asked Jul 31 at 21:20
einar
1238
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $p$ be a prime number and $a$,$b$ be two positive integers.
Show that
beginequation
a^p equiv_p b^p implies a equiv_p b
endequation
I'm thinking the best way to show this relationship is using Fermat's Little Theorem two times?
Maybe this can be done simply using the properties of Modular arithmetics?
FLT states that if $p$ is a prime number, then for any integer $a$, the number $a^p-a$ is an integer multiple of $p$.
Expressed :
$a^p equiv_p a$
I'm not sure how to apply FLT in this case, any help would be much appreciated!
elementary-number-theory modular-arithmetic
edited Jul 31 at 21:29
amWhy
189k25219431
asked Jul 31 at 21:20
einar
1238
Let $p$ be a prime number and $a$,$b$ be two positive integers.
Show that
beginequation
a^p equiv_p b^p implies a equiv_p b
endequation
I'm thinking the best way to show this relationship is using Fermat's Little Theorem two times?
Maybe this can be done simply using the properties of Modular arithmetics?
FLT states that if $p$ is a prime number, then for any integer $a$, the number $a^p-a$ is an integer multiple of $p$.
Expressed :
$a^p equiv_p a$
I'm not sure how to apply FLT in this case, any help would be much appreciated!
elementary-number-theory modular-arithmetic
edited Jul 31 at 21:29
amWhy
189k25219431
asked Jul 31 at 21:20
einar
1238
edited Jul 31 at 21:29
amWhy
189k25219431
edited Jul 31 at 21:29
amWhy
189k25219431
edited Jul 31 at 21:29
amWhy
189k25219431
189k25219431
asked Jul 31 at 21:20
einar
1238
asked Jul 31 at 21:20
einar
1238
asked Jul 31 at 21:20
einar
1238
1238
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
4
down vote
accepted
Observe that, any prime $p|binompr$ for $rin 1,2,cdots ,p-1$. Hence, we have $$(a-b)^pequiv_p a^p-binomp1a^p-1cdot b+cdots +binompp-1acdot b^p-1-b^p equiv_p a^p-b^p$$
For $p=2$, you need some effort - $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Now as you have $a^pequiv_p b^p$, you get $$(a-b)^pequiv_p a^p-b^pequiv_p 0$$ or, $aequiv_p b$.
answered Jul 31 at 21:34
tarit goswami
987
1
Why do you need $p$ to be odd with your method?
– Arnaud Mortier
Jul 31 at 21:36
1
Ok, $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Thanks!
– tarit goswami
Jul 31 at 21:38
You can also prove Fermat's little theorem this way
– Rumpelstiltskin
Jul 31 at 21:42
add a comment |Â
up vote
3
down vote
Note that
$$
aequiv_pa^pequiv_p b^pequiv_p b
$$
where the outer equalities are consequences of Fermat's Little Theorem.
answered Jul 31 at 21:22
Foobaz John
18k41245
add a comment |Â
up vote
2
down vote
Your idea (applying FLT twice) is fine:$$aequiv_pa^pequiv_pb^pequiv b.$$
answered Jul 31 at 21:22
José Carlos Santos
112k1696172
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
Observe that, any prime $p|binompr$ for $rin 1,2,cdots ,p-1$. Hence, we have $$(a-b)^pequiv_p a^p-binomp1a^p-1cdot b+cdots +binompp-1acdot b^p-1-b^p equiv_p a^p-b^p$$
For $p=2$, you need some effort - $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Now as you have $a^pequiv_p b^p$, you get $$(a-b)^pequiv_p a^p-b^pequiv_p 0$$ or, $aequiv_p b$.
answered Jul 31 at 21:34
tarit goswami
987
1
Why do you need $p$ to be odd with your method?
– Arnaud Mortier
Jul 31 at 21:36
1
Ok, $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Thanks!
– tarit goswami
Jul 31 at 21:38
You can also prove Fermat's little theorem this way
– Rumpelstiltskin
Jul 31 at 21:42
add a comment |Â
up vote
4
down vote
accepted
Observe that, any prime $p|binompr$ for $rin 1,2,cdots ,p-1$. Hence, we have $$(a-b)^pequiv_p a^p-binomp1a^p-1cdot b+cdots +binompp-1acdot b^p-1-b^p equiv_p a^p-b^p$$
For $p=2$, you need some effort - $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Now as you have $a^pequiv_p b^p$, you get $$(a-b)^pequiv_p a^p-b^pequiv_p 0$$ or, $aequiv_p b$.
answered Jul 31 at 21:34
tarit goswami
987
1
Why do you need $p$ to be odd with your method?
– Arnaud Mortier
Jul 31 at 21:36
1
Ok, $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Thanks!
– tarit goswami
Jul 31 at 21:38
You can also prove Fermat's little theorem this way
– Rumpelstiltskin
Jul 31 at 21:42
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
Observe that, any prime $p|binompr$ for $rin 1,2,cdots ,p-1$. Hence, we have $$(a-b)^pequiv_p a^p-binomp1a^p-1cdot b+cdots +binompp-1acdot b^p-1-b^p equiv_p a^p-b^p$$
For $p=2$, you need some effort - $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Now as you have $a^pequiv_p b^p$, you get $$(a-b)^pequiv_p a^p-b^pequiv_p 0$$ or, $aequiv_p b$.
answered Jul 31 at 21:34
tarit goswami
987
Observe that, any prime $p|binompr$ for $rin 1,2,cdots ,p-1$. Hence, we have $$(a-b)^pequiv_p a^p-binomp1a^p-1cdot b+cdots +binompp-1acdot b^p-1-b^p equiv_p a^p-b^p$$
For $p=2$, you need some effort - $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Now as you have $a^pequiv_p b^p$, you get $$(a-b)^pequiv_p a^p-b^pequiv_p 0$$ or, $aequiv_p b$.
answered Jul 31 at 21:34
tarit goswami
987
edited Jul 31 at 21:40
answered Jul 31 at 21:34
tarit goswami
987
answered Jul 31 at 21:34
tarit goswami
987
answered Jul 31 at 21:34
tarit goswami
987
987
1
Why do you need $p$ to be odd with your method?
– Arnaud Mortier
Jul 31 at 21:36
1
Ok, $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Thanks!
– tarit goswami
Jul 31 at 21:38
You can also prove Fermat's little theorem this way
– Rumpelstiltskin
Jul 31 at 21:42
add a comment |Â
1
Why do you need $p$ to be odd with your method?
– Arnaud Mortier
Jul 31 at 21:36
1
Ok, $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Thanks!
– tarit goswami
Jul 31 at 21:38
You can also prove Fermat's little theorem this way
– Rumpelstiltskin
Jul 31 at 21:42
1
1
Why do you need $p$ to be odd with your method?
– Arnaud Mortier
Jul 31 at 21:36
Why do you need $p$ to be odd with your method?
– Arnaud Mortier
Jul 31 at 21:36
1
1
Ok, $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Thanks!
– tarit goswami
Jul 31 at 21:38
Ok, $(a-b)^2equiv_2 a^2+b^2equiv_2 a^2-b^2$. Thanks!
– tarit goswami
Jul 31 at 21:38
You can also prove Fermat's little theorem this way
– Rumpelstiltskin
Jul 31 at 21:42
You can also prove Fermat's little theorem this way
– Rumpelstiltskin
Jul 31 at 21:42
add a comment |Â
up vote
3
down vote
Note that
$$
aequiv_pa^pequiv_p b^pequiv_p b
$$
where the outer equalities are consequences of Fermat's Little Theorem.
answered Jul 31 at 21:22
Foobaz John
18k41245
add a comment |Â
up vote
3
down vote
Note that
$$
aequiv_pa^pequiv_p b^pequiv_p b
$$
where the outer equalities are consequences of Fermat's Little Theorem.
answered Jul 31 at 21:22
Foobaz John
18k41245
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Note that
$$
aequiv_pa^pequiv_p b^pequiv_p b
$$
where the outer equalities are consequences of Fermat's Little Theorem.
answered Jul 31 at 21:22
Foobaz John
18k41245
Note that
$$
aequiv_pa^pequiv_p b^pequiv_p b
$$
where the outer equalities are consequences of Fermat's Little Theorem.
answered Jul 31 at 21:22
Foobaz John
18k41245
answered Jul 31 at 21:22
Foobaz John
18k41245
answered Jul 31 at 21:22
Foobaz John
18k41245
answered Jul 31 at 21:22
Foobaz John
18k41245
18k41245
add a comment |Â
add a comment |Â
up vote
2
down vote
Your idea (applying FLT twice) is fine:$$aequiv_pa^pequiv_pb^pequiv b.$$
answered Jul 31 at 21:22
José Carlos Santos
112k1696172
add a comment |Â
up vote
2
down vote
Your idea (applying FLT twice) is fine:$$aequiv_pa^pequiv_pb^pequiv b.$$
answered Jul 31 at 21:22
José Carlos Santos
112k1696172
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Your idea (applying FLT twice) is fine:$$aequiv_pa^pequiv_pb^pequiv b.$$
answered Jul 31 at 21:22
José Carlos Santos
112k1696172
Your idea (applying FLT twice) is fine:$$aequiv_pa^pequiv_pb^pequiv b.$$
answered Jul 31 at 21:22
José Carlos Santos
112k1696172
answered Jul 31 at 21:22
José Carlos Santos
112k1696172
answered Jul 31 at 21:22
José Carlos Santos
112k1696172
answered Jul 31 at 21:22
José Carlos Santos
112k1696172
112k1696172
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868498%2fapplying-fermats-little-theorem-to-show-ap-equiv-p-bp-implies-a-equiv-p%23new-answer', 'question_page');
);
Post as a guest
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
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
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