Mixing
Smallest cube ending in $2017$
Clash Royale CLAN TAG#URR8PPP
up vote
15
down vote
favorite
What is the smallest cube ending in $2017$?
My try: I know that the only possible units digit is $3$,
$$(a+3)^3 = 2017 mod 10^4;$$
and
$$a^3 + 9a^2 + 27a = 1990mod 10^4$$
I don't know how to proceed, I tried factoring and adding $10^5$ and $1990$ but when I saw the answer, this approach would take forever.
modular-arithmetic
edited Aug 12 at 21:57
Xander Henderson
13.2k83150
asked Aug 12 at 11:52
SuperMage1
707210
add a comment |Â
up vote
15
down vote
favorite
What is the smallest cube ending in $2017$?
My try: I know that the only possible units digit is $3$,
$$(a+3)^3 = 2017 mod 10^4;$$
and
$$a^3 + 9a^2 + 27a = 1990mod 10^4$$
I don't know how to proceed, I tried factoring and adding $10^5$ and $1990$ but when I saw the answer, this approach would take forever.
modular-arithmetic
edited Aug 12 at 21:57
Xander Henderson
13.2k83150
asked Aug 12 at 11:52
SuperMage1
707210
6
You should use $10a+3$ instead of $a+3$ since $3$ is the units digit, and that will help you to make more progress.
– Mark Bennet
Aug 12 at 11:55
3
It's rather modulo $10^4$
– Arnaud Mortier
Aug 12 at 11:55
add a comment |Â
up vote
15
down vote
favorite
up vote
15
down vote
favorite
What is the smallest cube ending in $2017$?
My try: I know that the only possible units digit is $3$,
$$(a+3)^3 = 2017 mod 10^4;$$
and
$$a^3 + 9a^2 + 27a = 1990mod 10^4$$
I don't know how to proceed, I tried factoring and adding $10^5$ and $1990$ but when I saw the answer, this approach would take forever.
modular-arithmetic
edited Aug 12 at 21:57
Xander Henderson
13.2k83150
asked Aug 12 at 11:52
SuperMage1
707210
What is the smallest cube ending in $2017$?
My try: I know that the only possible units digit is $3$,
$$(a+3)^3 = 2017 mod 10^4;$$
and
$$a^3 + 9a^2 + 27a = 1990mod 10^4$$
I don't know how to proceed, I tried factoring and adding $10^5$ and $1990$ but when I saw the answer, this approach would take forever.
modular-arithmetic
edited Aug 12 at 21:57
Xander Henderson
13.2k83150
asked Aug 12 at 11:52
SuperMage1
707210
edited Aug 12 at 21:57
Xander Henderson
13.2k83150
edited Aug 12 at 21:57
Xander Henderson
13.2k83150
edited Aug 12 at 21:57
Xander Henderson
13.2k83150
13.2k83150
asked Aug 12 at 11:52
SuperMage1
707210
asked Aug 12 at 11:52
SuperMage1
707210
asked Aug 12 at 11:52
SuperMage1
707210
707210
6
You should use $10a+3$ instead of $a+3$ since $3$ is the units digit, and that will help you to make more progress.
– Mark Bennet
Aug 12 at 11:55
3
It's rather modulo $10^4$
– Arnaud Mortier
Aug 12 at 11:55
add a comment |Â
6
You should use $10a+3$ instead of $a+3$ since $3$ is the units digit, and that will help you to make more progress.
– Mark Bennet
Aug 12 at 11:55
3
It's rather modulo $10^4$
– Arnaud Mortier
Aug 12 at 11:55
6
6
You should use $10a+3$ instead of $a+3$ since $3$ is the units digit, and that will help you to make more progress.
– Mark Bennet
Aug 12 at 11:55
You should use $10a+3$ instead of $a+3$ since $3$ is the units digit, and that will help you to make more progress.
– Mark Bennet
Aug 12 at 11:55
3
3
It's rather modulo $10^4$
– Arnaud Mortier
Aug 12 at 11:55
It's rather modulo $10^4$
– Arnaud Mortier
Aug 12 at 11:55
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
12
down vote
Recall Carmichael's theorem: $a^lambda(m) equiv 1 bmod m$ for all $a$ coprime with $m$.
For $lambda(10^4)=500$, we get $1 + 500 = 167 cdot 3$ and so $a equiv a cdot 1 equiv a cdot a^500 equiv (a^167)^3 bmod 10^4$.
Thus, the answer is $2017^167 bmod 10^4$, which is $9073$, by repeated squaring.
There is only one solution mod $10^4$ because $x mapsto x^3$ is injective in $U(10^4)$, as we have seen above.
answered Aug 12 at 12:07
lhf
156k9161368
Which formula you have used for the last deduction
– lab bhattacharjee
Aug 12 at 13:17
@user202729, see my edited answer
– lhf
Aug 12 at 16:29
add a comment |Â
up vote
11
down vote
$x^3equiv 7 pmod 10$. So $xequiv 3 pmod 10$.
Put $x=10y+3$, and compute $pmod 100$.
This yields $1000y^3+900y^2+270y+27 equiv 17 pmod 100$. Thus $70y equiv -10 pmod 100$, or equivalently, $7y equiv -1 pmod 10$. Divide by $7$: $y equiv 7 pmod 10$.
Put $y=10z+7$, hence $x=100z+73$. I think you see the pattern now: calculate modulo $1000$, it gives you the $pmod10$ remainder of $z$, and one more iteration gives you the $pmod 10000$ remainder of $x$, which is also the smallest solution.
(Solution: $9073$)
answered Aug 12 at 12:07
A. Pongrácz
4,137725
add a comment |Â
up vote
8
down vote
$a^3 + 9a^2 + 27a = 1990mod 10^4Longleftrightarrowcasesa^3 + 9a^2 + 27a = 1990mod 2^4\a^3 + 9a^2 + 27a = 1990mod 5^4\$
Now $2^4=16$, so the first equation is easy and happens to have only one solution, $14bmod 16$.
As for the second, the only solution is $320bmod 625$.
By the CRT, the only solution modulo $10000$ is $9070$, resulting in the least solution $$9073^3=746883272017$$
answered Aug 12 at 12:20
Arnaud Mortier
19.6k22159
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
12
down vote
Recall Carmichael's theorem: $a^lambda(m) equiv 1 bmod m$ for all $a$ coprime with $m$.
For $lambda(10^4)=500$, we get $1 + 500 = 167 cdot 3$ and so $a equiv a cdot 1 equiv a cdot a^500 equiv (a^167)^3 bmod 10^4$.
Thus, the answer is $2017^167 bmod 10^4$, which is $9073$, by repeated squaring.
There is only one solution mod $10^4$ because $x mapsto x^3$ is injective in $U(10^4)$, as we have seen above.
answered Aug 12 at 12:07
lhf
156k9161368
Which formula you have used for the last deduction
– lab bhattacharjee
Aug 12 at 13:17
@user202729, see my edited answer
– lhf
Aug 12 at 16:29
add a comment |Â
up vote
12
down vote
Recall Carmichael's theorem: $a^lambda(m) equiv 1 bmod m$ for all $a$ coprime with $m$.
For $lambda(10^4)=500$, we get $1 + 500 = 167 cdot 3$ and so $a equiv a cdot 1 equiv a cdot a^500 equiv (a^167)^3 bmod 10^4$.
Thus, the answer is $2017^167 bmod 10^4$, which is $9073$, by repeated squaring.
There is only one solution mod $10^4$ because $x mapsto x^3$ is injective in $U(10^4)$, as we have seen above.
answered Aug 12 at 12:07
lhf
156k9161368
Which formula you have used for the last deduction
– lab bhattacharjee
Aug 12 at 13:17
@user202729, see my edited answer
– lhf
Aug 12 at 16:29
add a comment |Â
up vote
12
down vote
up vote
12
down vote
Recall Carmichael's theorem: $a^lambda(m) equiv 1 bmod m$ for all $a$ coprime with $m$.
For $lambda(10^4)=500$, we get $1 + 500 = 167 cdot 3$ and so $a equiv a cdot 1 equiv a cdot a^500 equiv (a^167)^3 bmod 10^4$.
Thus, the answer is $2017^167 bmod 10^4$, which is $9073$, by repeated squaring.
There is only one solution mod $10^4$ because $x mapsto x^3$ is injective in $U(10^4)$, as we have seen above.
answered Aug 12 at 12:07
lhf
156k9161368
Recall Carmichael's theorem: $a^lambda(m) equiv 1 bmod m$ for all $a$ coprime with $m$.
For $lambda(10^4)=500$, we get $1 + 500 = 167 cdot 3$ and so $a equiv a cdot 1 equiv a cdot a^500 equiv (a^167)^3 bmod 10^4$.
Thus, the answer is $2017^167 bmod 10^4$, which is $9073$, by repeated squaring.
There is only one solution mod $10^4$ because $x mapsto x^3$ is injective in $U(10^4)$, as we have seen above.
answered Aug 12 at 12:07
lhf
156k9161368
edited Aug 12 at 15:55
answered Aug 12 at 12:07
lhf
156k9161368
answered Aug 12 at 12:07
lhf
156k9161368
answered Aug 12 at 12:07
lhf
156k9161368
156k9161368
Which formula you have used for the last deduction
– lab bhattacharjee
Aug 12 at 13:17
@user202729, see my edited answer
– lhf
Aug 12 at 16:29
add a comment |Â
Which formula you have used for the last deduction
– lab bhattacharjee
Aug 12 at 13:17
@user202729, see my edited answer
– lhf
Aug 12 at 16:29
Which formula you have used for the last deduction
– lab bhattacharjee
Aug 12 at 13:17
Which formula you have used for the last deduction
– lab bhattacharjee
Aug 12 at 13:17
@user202729, see my edited answer
– lhf
Aug 12 at 16:29
@user202729, see my edited answer
– lhf
Aug 12 at 16:29
add a comment |Â
up vote
11
down vote
$x^3equiv 7 pmod 10$. So $xequiv 3 pmod 10$.
Put $x=10y+3$, and compute $pmod 100$.
This yields $1000y^3+900y^2+270y+27 equiv 17 pmod 100$. Thus $70y equiv -10 pmod 100$, or equivalently, $7y equiv -1 pmod 10$. Divide by $7$: $y equiv 7 pmod 10$.
Put $y=10z+7$, hence $x=100z+73$. I think you see the pattern now: calculate modulo $1000$, it gives you the $pmod10$ remainder of $z$, and one more iteration gives you the $pmod 10000$ remainder of $x$, which is also the smallest solution.
(Solution: $9073$)
answered Aug 12 at 12:07
A. Pongrácz
4,137725
add a comment |Â
up vote
11
down vote
$x^3equiv 7 pmod 10$. So $xequiv 3 pmod 10$.
Put $x=10y+3$, and compute $pmod 100$.
This yields $1000y^3+900y^2+270y+27 equiv 17 pmod 100$. Thus $70y equiv -10 pmod 100$, or equivalently, $7y equiv -1 pmod 10$. Divide by $7$: $y equiv 7 pmod 10$.
Put $y=10z+7$, hence $x=100z+73$. I think you see the pattern now: calculate modulo $1000$, it gives you the $pmod10$ remainder of $z$, and one more iteration gives you the $pmod 10000$ remainder of $x$, which is also the smallest solution.
(Solution: $9073$)
answered Aug 12 at 12:07
A. Pongrácz
4,137725
add a comment |Â
up vote
11
down vote
up vote
11
down vote
$x^3equiv 7 pmod 10$. So $xequiv 3 pmod 10$.
Put $x=10y+3$, and compute $pmod 100$.
This yields $1000y^3+900y^2+270y+27 equiv 17 pmod 100$. Thus $70y equiv -10 pmod 100$, or equivalently, $7y equiv -1 pmod 10$. Divide by $7$: $y equiv 7 pmod 10$.
Put $y=10z+7$, hence $x=100z+73$. I think you see the pattern now: calculate modulo $1000$, it gives you the $pmod10$ remainder of $z$, and one more iteration gives you the $pmod 10000$ remainder of $x$, which is also the smallest solution.
(Solution: $9073$)
answered Aug 12 at 12:07
A. Pongrácz
4,137725
$x^3equiv 7 pmod 10$. So $xequiv 3 pmod 10$.
Put $x=10y+3$, and compute $pmod 100$.
This yields $1000y^3+900y^2+270y+27 equiv 17 pmod 100$. Thus $70y equiv -10 pmod 100$, or equivalently, $7y equiv -1 pmod 10$. Divide by $7$: $y equiv 7 pmod 10$.
Put $y=10z+7$, hence $x=100z+73$. I think you see the pattern now: calculate modulo $1000$, it gives you the $pmod10$ remainder of $z$, and one more iteration gives you the $pmod 10000$ remainder of $x$, which is also the smallest solution.
(Solution: $9073$)
answered Aug 12 at 12:07
A. Pongrácz
4,137725
edited Aug 12 at 12:12
answered Aug 12 at 12:07
A. Pongrácz
4,137725
answered Aug 12 at 12:07
A. Pongrácz
4,137725
answered Aug 12 at 12:07
A. Pongrácz
4,137725
4,137725
add a comment |Â
add a comment |Â
up vote
8
down vote
$a^3 + 9a^2 + 27a = 1990mod 10^4Longleftrightarrowcasesa^3 + 9a^2 + 27a = 1990mod 2^4\a^3 + 9a^2 + 27a = 1990mod 5^4\$
Now $2^4=16$, so the first equation is easy and happens to have only one solution, $14bmod 16$.
As for the second, the only solution is $320bmod 625$.
By the CRT, the only solution modulo $10000$ is $9070$, resulting in the least solution $$9073^3=746883272017$$
answered Aug 12 at 12:20
Arnaud Mortier
19.6k22159
add a comment |Â
up vote
8
down vote
$a^3 + 9a^2 + 27a = 1990mod 10^4Longleftrightarrowcasesa^3 + 9a^2 + 27a = 1990mod 2^4\a^3 + 9a^2 + 27a = 1990mod 5^4\$
Now $2^4=16$, so the first equation is easy and happens to have only one solution, $14bmod 16$.
As for the second, the only solution is $320bmod 625$.
By the CRT, the only solution modulo $10000$ is $9070$, resulting in the least solution $$9073^3=746883272017$$
answered Aug 12 at 12:20
Arnaud Mortier
19.6k22159
add a comment |Â
up vote
8
down vote
up vote
8
down vote
$a^3 + 9a^2 + 27a = 1990mod 10^4Longleftrightarrowcasesa^3 + 9a^2 + 27a = 1990mod 2^4\a^3 + 9a^2 + 27a = 1990mod 5^4\$
Now $2^4=16$, so the first equation is easy and happens to have only one solution, $14bmod 16$.
As for the second, the only solution is $320bmod 625$.
By the CRT, the only solution modulo $10000$ is $9070$, resulting in the least solution $$9073^3=746883272017$$
answered Aug 12 at 12:20
Arnaud Mortier
19.6k22159
$a^3 + 9a^2 + 27a = 1990mod 10^4Longleftrightarrowcasesa^3 + 9a^2 + 27a = 1990mod 2^4\a^3 + 9a^2 + 27a = 1990mod 5^4\$
Now $2^4=16$, so the first equation is easy and happens to have only one solution, $14bmod 16$.
As for the second, the only solution is $320bmod 625$.
By the CRT, the only solution modulo $10000$ is $9070$, resulting in the least solution $$9073^3=746883272017$$
answered Aug 12 at 12:20
Arnaud Mortier
19.6k22159
answered Aug 12 at 12:20
Arnaud Mortier
19.6k22159
answered Aug 12 at 12:20
Arnaud Mortier
19.6k22159
answered Aug 12 at 12:20
Arnaud Mortier
19.6k22159
19.6k22159
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%2f2880243%2fsmallest-cube-ending-in-2017%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
6
You should use $10a+3$ instead of $a+3$ since $3$ is the units digit, and that will help you to make more progress.
– Mark Bennet
Aug 12 at 11:55
3
It's rather modulo $10^4$
– Arnaud Mortier
Aug 12 at 11:55