Finding prime factors of large expression (without calculator)

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

Show that: $5^3(5^3(253)+3)+1 = 19 times 251 times 829$.

I tried setting $n=5$, so that $253 = 23 times 11 = (4n+3)(2n+1)$ and going from there, but the resulting polynomial in $n$ was $8n^6 + 10n^7 + 3n^6 + 3n^3 + 1$, which turns out to be irreducible over the integers, so this doesn't help at all.

algebra-precalculus elementary-number-theory

share|cite|improve this question

asked Jul 21 at 15:04

Prasiortle

463

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You tried setting $n=5$ in what? Also, your polynomial in $n$ is given in a strange manner.
  – vadim123
  Jul 21 at 15:11
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just set $n=5$ so that the expression could be rewritten as $n^3(n^3(4n+3)(2n+1)+3)+1$.
  – Prasiortle
  Jul 21 at 15:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I think you meant to write $8n^8$ rather than $8n^6,$ for what it's worth.
  – David K
  Jul 21 at 17:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Trying to set $n=5^3$ will help if you write $253=2cdot5^3+3$ as $2n+3$. You have $2n^3+3n^2+3n+1=(2n+1)(n^2+n+1)$. Both $n^2+n+1$ and $n^6+n^3+1$ (if you set $n=5$ instead) are irreducible, so further factorization needs another trick,
  – Jyrki Lahtonen
  Jul 22 at 22:30
  
  

  
  
  
  

add a comment | 

up vote
2
down vote

favorite

Show that: $5^3(5^3(253)+3)+1 = 19 times 251 times 829$.

I tried setting $n=5$, so that $253 = 23 times 11 = (4n+3)(2n+1)$ and going from there, but the resulting polynomial in $n$ was $8n^6 + 10n^7 + 3n^6 + 3n^3 + 1$, which turns out to be irreducible over the integers, so this doesn't help at all.

algebra-precalculus elementary-number-theory

share|cite|improve this question

asked Jul 21 at 15:04

Prasiortle

463

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You tried setting $n=5$ in what? Also, your polynomial in $n$ is given in a strange manner.
  – vadim123
  Jul 21 at 15:11
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just set $n=5$ so that the expression could be rewritten as $n^3(n^3(4n+3)(2n+1)+3)+1$.
  – Prasiortle
  Jul 21 at 15:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I think you meant to write $8n^8$ rather than $8n^6,$ for what it's worth.
  – David K
  Jul 21 at 17:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Trying to set $n=5^3$ will help if you write $253=2cdot5^3+3$ as $2n+3$. You have $2n^3+3n^2+3n+1=(2n+1)(n^2+n+1)$. Both $n^2+n+1$ and $n^6+n^3+1$ (if you set $n=5$ instead) are irreducible, so further factorization needs another trick,
  – Jyrki Lahtonen
  Jul 22 at 22:30
  
  

  
  
  
  

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

Show that: $5^3(5^3(253)+3)+1 = 19 times 251 times 829$.

I tried setting $n=5$, so that $253 = 23 times 11 = (4n+3)(2n+1)$ and going from there, but the resulting polynomial in $n$ was $8n^6 + 10n^7 + 3n^6 + 3n^3 + 1$, which turns out to be irreducible over the integers, so this doesn't help at all.

algebra-precalculus elementary-number-theory

share|cite|improve this question

asked Jul 21 at 15:04

Prasiortle

463

Show that: $5^3(5^3(253)+3)+1 = 19 times 251 times 829$.

I tried setting $n=5$, so that $253 = 23 times 11 = (4n+3)(2n+1)$ and going from there, but the resulting polynomial in $n$ was $8n^6 + 10n^7 + 3n^6 + 3n^3 + 1$, which turns out to be irreducible over the integers, so this doesn't help at all.

algebra-precalculus elementary-number-theory

share|cite|improve this question

asked Jul 21 at 15:04

Prasiortle

463

share|cite|improve this question

share|cite|improve this question

asked Jul 21 at 15:04

Prasiortle

463

asked Jul 21 at 15:04

Prasiortle

463

asked Jul 21 at 15:04

Prasiortle

463

463

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You tried setting $n=5$ in what? Also, your polynomial in $n$ is given in a strange manner.
  – vadim123
  Jul 21 at 15:11
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just set $n=5$ so that the expression could be rewritten as $n^3(n^3(4n+3)(2n+1)+3)+1$.
  – Prasiortle
  Jul 21 at 15:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I think you meant to write $8n^8$ rather than $8n^6,$ for what it's worth.
  – David K
  Jul 21 at 17:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Trying to set $n=5^3$ will help if you write $253=2cdot5^3+3$ as $2n+3$. You have $2n^3+3n^2+3n+1=(2n+1)(n^2+n+1)$. Both $n^2+n+1$ and $n^6+n^3+1$ (if you set $n=5$ instead) are irreducible, so further factorization needs another trick,
  – Jyrki Lahtonen
  Jul 22 at 22:30
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You tried setting $n=5$ in what? Also, your polynomial in $n$ is given in a strange manner.
  – vadim123
  Jul 21 at 15:11
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just set $n=5$ so that the expression could be rewritten as $n^3(n^3(4n+3)(2n+1)+3)+1$.
  – Prasiortle
  Jul 21 at 15:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I think you meant to write $8n^8$ rather than $8n^6,$ for what it's worth.
  – David K
  Jul 21 at 17:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Trying to set $n=5^3$ will help if you write $253=2cdot5^3+3$ as $2n+3$. You have $2n^3+3n^2+3n+1=(2n+1)(n^2+n+1)$. Both $n^2+n+1$ and $n^6+n^3+1$ (if you set $n=5$ instead) are irreducible, so further factorization needs another trick,
  – Jyrki Lahtonen
  Jul 22 at 22:30
  
  

  
  
  
  

1

1

You tried setting $n=5$ in what? Also, your polynomial in $n$ is given in a strange manner.
– vadim123
Jul 21 at 15:11

You tried setting $n=5$ in what? Also, your polynomial in $n$ is given in a strange manner.
– vadim123
Jul 21 at 15:11

I just set $n=5$ so that the expression could be rewritten as $n^3(n^3(4n+3)(2n+1)+3)+1$.
– Prasiortle
Jul 21 at 15:34

I just set $n=5$ so that the expression could be rewritten as $n^3(n^3(4n+3)(2n+1)+3)+1$.
– Prasiortle
Jul 21 at 15:34

I think you meant to write $8n^8$ rather than $8n^6,$ for what it's worth.
– David K
Jul 21 at 17:11

I think you meant to write $8n^8$ rather than $8n^6,$ for what it's worth.
– David K
Jul 21 at 17:11

Trying to set $n=5^3$ will help if you write $253=2cdot5^3+3$ as $2n+3$. You have $2n^3+3n^2+3n+1=(2n+1)(n^2+n+1)$. Both $n^2+n+1$ and $n^6+n^3+1$ (if you set $n=5$ instead) are irreducible, so further factorization needs another trick,
– Jyrki Lahtonen
Jul 22 at 22:30

Trying to set $n=5^3$ will help if you write $253=2cdot5^3+3$ as $2n+3$. You have $2n^3+3n^2+3n+1=(2n+1)(n^2+n+1)$. Both $n^2+n+1$ and $n^6+n^3+1$ (if you set $n=5$ instead) are irreducible, so further factorization needs another trick,
– Jyrki Lahtonen
Jul 22 at 22:30

add a comment | 

2 Answers
2

active

oldest

votes

up vote
0
down vote

My eye is drawn to the $253$ in the expression being close to the factor $251$ and the fact that $5^3$ is very close to half of $251$. Given the known result I would write
$$5^3(5^3(253)+3)+1=5^3(5^3cdot (251+2)+3)+1\=5^6cdot 251+5^3cdot253+1\=(5^6+5^3+1)251$$
then just compute $5^6+5^3+1=15625+125+1=15751$ and divide by $19$

share|cite|improve this answer

edited Jul 21 at 20:05

answered Jul 21 at 15:28

Ross Millikan

276k21186352

add a comment | 

up vote
-1
down vote

Divide $19*251*829$ by $5$ and take remainders.

$19*251*829 = 19*250*829 + 19*830 -20 + 1=$

$5(19*50*829 + 19*166 -4) + 1=$

$5(19*50*829 + 19*165 + 20 -5) + 1=$

$5(19*10*829 + 19*33 + 3) + 1=$

$5^2(19*10*829 + 20*33 -30) + 1=$

$5^3(19*2*829 + 4*33 -6) + 1=$

$5^3(19*2*830 -20*2 + 2 + 5*33 - 30 - 3-6) + 1=$

$5^3(19*2*830 - 20*2 + 5*33 -30 -10 +3) + 1=$

$5^3(5(19*2*166 - 4*2 + 33 -8) +3) + 1=$

$5^3(5(19*2*165 + 20*2 -10 + 30 -5)+3) + 1=$

$5^3(5^2(19*2*33 + 4*2 + 3)+3) + 1=$

$5^3(5^2(19*2*33 + 11)+3) +1=$

$5^3(5^2(20*2*33 - 2*33+11)+3)+1=$

$5^3(5^2(20*2*33 - 2*30-6+11)+3)+1=$

$5^3(5^3(4*2*33 -2*6 +1)+3)+1=$

$5^3(5^3(5*2*33 - 2*30 - 3*5 -3 +1)+3)+1=$

$5^3(5^3(330 - 60 -15 -2)+3)+1=$

$5^3(5^3(253)+3)+1=$

share|cite|improve this answer

answered Jul 22 at 4:17

fleablood

60.4k22575

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858564%2ffinding-prime-factors-of-large-expression-without-calculator%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote

My eye is drawn to the $253$ in the expression being close to the factor $251$ and the fact that $5^3$ is very close to half of $251$. Given the known result I would write
$$5^3(5^3(253)+3)+1=5^3(5^3cdot (251+2)+3)+1\=5^6cdot 251+5^3cdot253+1\=(5^6+5^3+1)251$$
then just compute $5^6+5^3+1=15625+125+1=15751$ and divide by $19$

share|cite|improve this answer

edited Jul 21 at 20:05

answered Jul 21 at 15:28

Ross Millikan

276k21186352

add a comment | 

up vote
0
down vote

My eye is drawn to the $253$ in the expression being close to the factor $251$ and the fact that $5^3$ is very close to half of $251$. Given the known result I would write
$$5^3(5^3(253)+3)+1=5^3(5^3cdot (251+2)+3)+1\=5^6cdot 251+5^3cdot253+1\=(5^6+5^3+1)251$$
then just compute $5^6+5^3+1=15625+125+1=15751$ and divide by $19$

share|cite|improve this answer

edited Jul 21 at 20:05

answered Jul 21 at 15:28

Ross Millikan

276k21186352

add a comment | 

up vote
0
down vote

up vote
0
down vote

My eye is drawn to the $253$ in the expression being close to the factor $251$ and the fact that $5^3$ is very close to half of $251$. Given the known result I would write
$$5^3(5^3(253)+3)+1=5^3(5^3cdot (251+2)+3)+1\=5^6cdot 251+5^3cdot253+1\=(5^6+5^3+1)251$$
then just compute $5^6+5^3+1=15625+125+1=15751$ and divide by $19$

share|cite|improve this answer

edited Jul 21 at 20:05

answered Jul 21 at 15:28

Ross Millikan

276k21186352

My eye is drawn to the $253$ in the expression being close to the factor $251$ and the fact that $5^3$ is very close to half of $251$. Given the known result I would write
$$5^3(5^3(253)+3)+1=5^3(5^3cdot (251+2)+3)+1\=5^6cdot 251+5^3cdot253+1\=(5^6+5^3+1)251$$
then just compute $5^6+5^3+1=15625+125+1=15751$ and divide by $19$

share|cite|improve this answer

edited Jul 21 at 20:05

answered Jul 21 at 15:28

Ross Millikan

276k21186352

share|cite|improve this answer

share|cite|improve this answer

edited Jul 21 at 20:05

edited Jul 21 at 20:05

edited Jul 21 at 20:05

answered Jul 21 at 15:28

Ross Millikan

276k21186352

answered Jul 21 at 15:28

Ross Millikan

276k21186352

answered Jul 21 at 15:28

Ross Millikan

276k21186352

276k21186352

add a comment | 

add a comment | 

up vote
-1
down vote

Divide $19*251*829$ by $5$ and take remainders.

$19*251*829 = 19*250*829 + 19*830 -20 + 1=$

$5(19*50*829 + 19*166 -4) + 1=$

$5(19*50*829 + 19*165 + 20 -5) + 1=$

$5(19*10*829 + 19*33 + 3) + 1=$

$5^2(19*10*829 + 20*33 -30) + 1=$

$5^3(19*2*829 + 4*33 -6) + 1=$

$5^3(19*2*830 -20*2 + 2 + 5*33 - 30 - 3-6) + 1=$

$5^3(19*2*830 - 20*2 + 5*33 -30 -10 +3) + 1=$

$5^3(5(19*2*166 - 4*2 + 33 -8) +3) + 1=$

$5^3(5(19*2*165 + 20*2 -10 + 30 -5)+3) + 1=$

$5^3(5^2(19*2*33 + 4*2 + 3)+3) + 1=$

$5^3(5^2(19*2*33 + 11)+3) +1=$

$5^3(5^2(20*2*33 - 2*33+11)+3)+1=$

$5^3(5^2(20*2*33 - 2*30-6+11)+3)+1=$

$5^3(5^3(4*2*33 -2*6 +1)+3)+1=$

$5^3(5^3(5*2*33 - 2*30 - 3*5 -3 +1)+3)+1=$

$5^3(5^3(330 - 60 -15 -2)+3)+1=$

$5^3(5^3(253)+3)+1=$

share|cite|improve this answer

answered Jul 22 at 4:17

fleablood

60.4k22575

add a comment | 

up vote
-1
down vote

Divide $19*251*829$ by $5$ and take remainders.

$19*251*829 = 19*250*829 + 19*830 -20 + 1=$

$5(19*50*829 + 19*166 -4) + 1=$

$5(19*50*829 + 19*165 + 20 -5) + 1=$

$5(19*10*829 + 19*33 + 3) + 1=$

$5^2(19*10*829 + 20*33 -30) + 1=$

$5^3(19*2*829 + 4*33 -6) + 1=$

$5^3(19*2*830 -20*2 + 2 + 5*33 - 30 - 3-6) + 1=$

$5^3(19*2*830 - 20*2 + 5*33 -30 -10 +3) + 1=$

$5^3(5(19*2*166 - 4*2 + 33 -8) +3) + 1=$

$5^3(5(19*2*165 + 20*2 -10 + 30 -5)+3) + 1=$

$5^3(5^2(19*2*33 + 4*2 + 3)+3) + 1=$

$5^3(5^2(19*2*33 + 11)+3) +1=$

$5^3(5^2(20*2*33 - 2*33+11)+3)+1=$

$5^3(5^2(20*2*33 - 2*30-6+11)+3)+1=$

$5^3(5^3(4*2*33 -2*6 +1)+3)+1=$

$5^3(5^3(5*2*33 - 2*30 - 3*5 -3 +1)+3)+1=$

$5^3(5^3(330 - 60 -15 -2)+3)+1=$

$5^3(5^3(253)+3)+1=$

share|cite|improve this answer

answered Jul 22 at 4:17

fleablood

60.4k22575

add a comment | 

up vote
-1
down vote

up vote
-1
down vote

Divide $19*251*829$ by $5$ and take remainders.

$19*251*829 = 19*250*829 + 19*830 -20 + 1=$

$5(19*50*829 + 19*166 -4) + 1=$

$5(19*50*829 + 19*165 + 20 -5) + 1=$

$5(19*10*829 + 19*33 + 3) + 1=$

$5^2(19*10*829 + 20*33 -30) + 1=$

$5^3(19*2*829 + 4*33 -6) + 1=$

$5^3(19*2*830 -20*2 + 2 + 5*33 - 30 - 3-6) + 1=$

$5^3(19*2*830 - 20*2 + 5*33 -30 -10 +3) + 1=$

$5^3(5(19*2*166 - 4*2 + 33 -8) +3) + 1=$

$5^3(5(19*2*165 + 20*2 -10 + 30 -5)+3) + 1=$

$5^3(5^2(19*2*33 + 4*2 + 3)+3) + 1=$

$5^3(5^2(19*2*33 + 11)+3) +1=$

$5^3(5^2(20*2*33 - 2*33+11)+3)+1=$

$5^3(5^2(20*2*33 - 2*30-6+11)+3)+1=$

$5^3(5^3(4*2*33 -2*6 +1)+3)+1=$

$5^3(5^3(5*2*33 - 2*30 - 3*5 -3 +1)+3)+1=$

$5^3(5^3(330 - 60 -15 -2)+3)+1=$

$5^3(5^3(253)+3)+1=$

share|cite|improve this answer

answered Jul 22 at 4:17

fleablood

60.4k22575

Divide $19*251*829$ by $5$ and take remainders.

$19*251*829 = 19*250*829 + 19*830 -20 + 1=$

$5(19*50*829 + 19*166 -4) + 1=$

$5(19*50*829 + 19*165 + 20 -5) + 1=$

$5(19*10*829 + 19*33 + 3) + 1=$

$5^2(19*10*829 + 20*33 -30) + 1=$

$5^3(19*2*829 + 4*33 -6) + 1=$

$5^3(19*2*830 -20*2 + 2 + 5*33 - 30 - 3-6) + 1=$

$5^3(19*2*830 - 20*2 + 5*33 -30 -10 +3) + 1=$

$5^3(5(19*2*166 - 4*2 + 33 -8) +3) + 1=$

$5^3(5(19*2*165 + 20*2 -10 + 30 -5)+3) + 1=$

$5^3(5^2(19*2*33 + 4*2 + 3)+3) + 1=$

$5^3(5^2(19*2*33 + 11)+3) +1=$

$5^3(5^2(20*2*33 - 2*33+11)+3)+1=$

$5^3(5^2(20*2*33 - 2*30-6+11)+3)+1=$

$5^3(5^3(4*2*33 -2*6 +1)+3)+1=$

$5^3(5^3(5*2*33 - 2*30 - 3*5 -3 +1)+3)+1=$

$5^3(5^3(330 - 60 -15 -2)+3)+1=$

$5^3(5^3(253)+3)+1=$

share|cite|improve this answer

answered Jul 22 at 4:17

fleablood

60.4k22575

share|cite|improve this answer

share|cite|improve this answer

answered Jul 22 at 4:17

fleablood

60.4k22575

answered Jul 22 at 4:17

fleablood

60.4k22575

answered Jul 22 at 4:17

fleablood

60.4k22575

60.4k22575

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858564%2ffinding-prime-factors-of-large-expression-without-calculator%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

Name Email

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

Name Email

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

Name Email

Name Email

Name

Email

Name Email

Name

Email