Mixing
Highest power of a number that divides a larger number?
$begingroup$
Is the method of prime factorization valid for finding
largest power of a number n such that n divides the number x also x>n?
E.g:-
Question: Highest power of 2 that divides $2^2 * 3^3 * 4^4 * 5^5 * 6^6$ ?
Ans: $16$ by using prime factorization for eliminating $2$ as $2^{16}$ will divide $2^2 * 3^3 * 4^4 * 5^5 * 6^6$.
Steps:
$2^2 * 3^3 * 4^4 * 5^5 * 6^6$.- $2^2 * 3^3 * 2^8 * 5^5 * 3^6 * 2^6 $
- $2^{16} * 3^9 * 5^5 $
- Now max power of 2 that can divide $2^{16} * 3^9 * 5^5 $ is $2^{16}$ only.
My doubt is after getting rid of $2^{16}$ from numerator in step 4 we still have
$3^9 * 5^5$ which can be divided using 2 though we won't get an integral solution so the approach using prime factorization is incorrect ?
Reference Video:-
https://www.youtube.com/watch?v=HNeiXfQ6EAk&list=PLK4eozjPKMfHJCRkHI34sOG7Pk5c31UTq&index=24
Also we cannot make use of calculator for solving this problem can anyone verify the method in the video if possible do describe an alternate method.
Thanks
prime-numbers prime-factorization
asked Jan 21 at 2:50
Yash PanchalYash Panchal
73
$endgroup$
add a comment |
$begingroup$
Is the method of prime factorization valid for finding
largest power of a number n such that n divides the number x also x>n?
E.g:-
Question: Highest power of 2 that divides $2^2 * 3^3 * 4^4 * 5^5 * 6^6$ ?
Ans: $16$ by using prime factorization for eliminating $2$ as $2^{16}$ will divide $2^2 * 3^3 * 4^4 * 5^5 * 6^6$.
Steps:
$2^2 * 3^3 * 4^4 * 5^5 * 6^6$.- $2^2 * 3^3 * 2^8 * 5^5 * 3^6 * 2^6 $
- $2^{16} * 3^9 * 5^5 $
- Now max power of 2 that can divide $2^{16} * 3^9 * 5^5 $ is $2^{16}$ only.
My doubt is after getting rid of $2^{16}$ from numerator in step 4 we still have
$3^9 * 5^5$ which can be divided using 2 though we won't get an integral solution so the approach using prime factorization is incorrect ?
Reference Video:-
https://www.youtube.com/watch?v=HNeiXfQ6EAk&list=PLK4eozjPKMfHJCRkHI34sOG7Pk5c31UTq&index=24
Also we cannot make use of calculator for solving this problem can anyone verify the method in the video if possible do describe an alternate method.
Thanks
prime-numbers prime-factorization
asked Jan 21 at 2:50
Yash PanchalYash Panchal
73
$endgroup$
$begingroup$
If you know a prime factor, it can be efficiently determined which exponent in the prime factorization belongs to it by repeated division. But to determine the maximum exponent is not significantly easier than integer factorization: In particular , no efficient method is known to decide whether a given number is squarefree.
$endgroup$
– Peter
Jan 21 at 11:54
$begingroup$
So as a general case whenever one is to find max possible power of a given number that divides a very large number one should only eliminate the prime factorized version of the large number to get integral solution rather than going for mixed fraction one?
$endgroup$
– Yash Panchal
Jan 21 at 15:24
$begingroup$
In practice, I would partially factor the number by trial division upto , lets say, $10^9$. If the number is not too large, more advanced methods can be applied. If the number cannot be completely factored in a reasonable time, we cannot determine the largest exponent for sure. But it is very likely that the number (when not especially constructed) is not divisible by the square of a prime larger than $10^9$, so we can quite safely assume that the partial factorization reveals the correct result.
$endgroup$
– Peter
Jan 22 at 10:40
$begingroup$
Without a calculator, you probably can only sucessfully determine the result, if the number has very small prime factors.
$endgroup$
– Peter
Jan 22 at 10:43
add a comment |
$begingroup$
Is the method of prime factorization valid for finding
largest power of a number n such that n divides the number x also x>n?
E.g:-
Question: Highest power of 2 that divides $2^2 * 3^3 * 4^4 * 5^5 * 6^6$ ?
Ans: $16$ by using prime factorization for eliminating $2$ as $2^{16}$ will divide $2^2 * 3^3 * 4^4 * 5^5 * 6^6$.
Steps:
$2^2 * 3^3 * 4^4 * 5^5 * 6^6$.- $2^2 * 3^3 * 2^8 * 5^5 * 3^6 * 2^6 $
- $2^{16} * 3^9 * 5^5 $
- Now max power of 2 that can divide $2^{16} * 3^9 * 5^5 $ is $2^{16}$ only.
My doubt is after getting rid of $2^{16}$ from numerator in step 4 we still have
$3^9 * 5^5$ which can be divided using 2 though we won't get an integral solution so the approach using prime factorization is incorrect ?
Reference Video:-
https://www.youtube.com/watch?v=HNeiXfQ6EAk&list=PLK4eozjPKMfHJCRkHI34sOG7Pk5c31UTq&index=24
Also we cannot make use of calculator for solving this problem can anyone verify the method in the video if possible do describe an alternate method.
Thanks
prime-numbers prime-factorization
asked Jan 21 at 2:50
Yash PanchalYash Panchal
73
$endgroup$
Is the method of prime factorization valid for finding
largest power of a number n such that n divides the number x also x>n?
E.g:-
Question: Highest power of 2 that divides $2^2 * 3^3 * 4^4 * 5^5 * 6^6$ ?
Ans: $16$ by using prime factorization for eliminating $2$ as $2^{16}$ will divide $2^2 * 3^3 * 4^4 * 5^5 * 6^6$.
Steps:
$2^2 * 3^3 * 4^4 * 5^5 * 6^6$.- $2^2 * 3^3 * 2^8 * 5^5 * 3^6 * 2^6 $
- $2^{16} * 3^9 * 5^5 $
- Now max power of 2 that can divide $2^{16} * 3^9 * 5^5 $ is $2^{16}$ only.
My doubt is after getting rid of $2^{16}$ from numerator in step 4 we still have
$3^9 * 5^5$ which can be divided using 2 though we won't get an integral solution so the approach using prime factorization is incorrect ?
Reference Video:-
https://www.youtube.com/watch?v=HNeiXfQ6EAk&list=PLK4eozjPKMfHJCRkHI34sOG7Pk5c31UTq&index=24
Also we cannot make use of calculator for solving this problem can anyone verify the method in the video if possible do describe an alternate method.
Thanks
prime-numbers prime-factorization
prime-numbers prime-factorization
asked Jan 21 at 2:50
Yash PanchalYash Panchal
73
asked Jan 21 at 2:50
Yash PanchalYash Panchal
73
edited Jan 21 at 9:05
Yash Panchal
asked Jan 21 at 2:50
Yash PanchalYash Panchal
73
asked Jan 21 at 2:50
Yash PanchalYash Panchal
73
asked Jan 21 at 2:50
Yash PanchalYash Panchal
73
73
$begingroup$
If you know a prime factor, it can be efficiently determined which exponent in the prime factorization belongs to it by repeated division. But to determine the maximum exponent is not significantly easier than integer factorization: In particular , no efficient method is known to decide whether a given number is squarefree.
$endgroup$
– Peter
Jan 21 at 11:54
$begingroup$
So as a general case whenever one is to find max possible power of a given number that divides a very large number one should only eliminate the prime factorized version of the large number to get integral solution rather than going for mixed fraction one?
$endgroup$
– Yash Panchal
Jan 21 at 15:24
$begingroup$
In practice, I would partially factor the number by trial division upto , lets say, $10^9$. If the number is not too large, more advanced methods can be applied. If the number cannot be completely factored in a reasonable time, we cannot determine the largest exponent for sure. But it is very likely that the number (when not especially constructed) is not divisible by the square of a prime larger than $10^9$, so we can quite safely assume that the partial factorization reveals the correct result.
$endgroup$
– Peter
Jan 22 at 10:40
$begingroup$
Without a calculator, you probably can only sucessfully determine the result, if the number has very small prime factors.
$endgroup$
– Peter
Jan 22 at 10:43
add a comment |
$begingroup$
If you know a prime factor, it can be efficiently determined which exponent in the prime factorization belongs to it by repeated division. But to determine the maximum exponent is not significantly easier than integer factorization: In particular , no efficient method is known to decide whether a given number is squarefree.
$endgroup$
– Peter
Jan 21 at 11:54
$begingroup$
So as a general case whenever one is to find max possible power of a given number that divides a very large number one should only eliminate the prime factorized version of the large number to get integral solution rather than going for mixed fraction one?
$endgroup$
– Yash Panchal
Jan 21 at 15:24
$begingroup$
In practice, I would partially factor the number by trial division upto , lets say, $10^9$. If the number is not too large, more advanced methods can be applied. If the number cannot be completely factored in a reasonable time, we cannot determine the largest exponent for sure. But it is very likely that the number (when not especially constructed) is not divisible by the square of a prime larger than $10^9$, so we can quite safely assume that the partial factorization reveals the correct result.
$endgroup$
– Peter
Jan 22 at 10:40
$begingroup$
Without a calculator, you probably can only sucessfully determine the result, if the number has very small prime factors.
$endgroup$
– Peter
Jan 22 at 10:43
$begingroup$
If you know a prime factor, it can be efficiently determined which exponent in the prime factorization belongs to it by repeated division. But to determine the maximum exponent is not significantly easier than integer factorization: In particular , no efficient method is known to decide whether a given number is squarefree.
$endgroup$
– Peter
Jan 21 at 11:54
$begingroup$
If you know a prime factor, it can be efficiently determined which exponent in the prime factorization belongs to it by repeated division. But to determine the maximum exponent is not significantly easier than integer factorization: In particular , no efficient method is known to decide whether a given number is squarefree.
$endgroup$
– Peter
Jan 21 at 11:54
$begingroup$
So as a general case whenever one is to find max possible power of a given number that divides a very large number one should only eliminate the prime factorized version of the large number to get integral solution rather than going for mixed fraction one?
$endgroup$
– Yash Panchal
Jan 21 at 15:24
$begingroup$
So as a general case whenever one is to find max possible power of a given number that divides a very large number one should only eliminate the prime factorized version of the large number to get integral solution rather than going for mixed fraction one?
$endgroup$
– Yash Panchal
Jan 21 at 15:24
$begingroup$
In practice, I would partially factor the number by trial division upto , lets say, $10^9$. If the number is not too large, more advanced methods can be applied. If the number cannot be completely factored in a reasonable time, we cannot determine the largest exponent for sure. But it is very likely that the number (when not especially constructed) is not divisible by the square of a prime larger than $10^9$, so we can quite safely assume that the partial factorization reveals the correct result.
$endgroup$
– Peter
Jan 22 at 10:40
$begingroup$
In practice, I would partially factor the number by trial division upto , lets say, $10^9$. If the number is not too large, more advanced methods can be applied. If the number cannot be completely factored in a reasonable time, we cannot determine the largest exponent for sure. But it is very likely that the number (when not especially constructed) is not divisible by the square of a prime larger than $10^9$, so we can quite safely assume that the partial factorization reveals the correct result.
$endgroup$
– Peter
Jan 22 at 10:40
$begingroup$
Without a calculator, you probably can only sucessfully determine the result, if the number has very small prime factors.
$endgroup$
– Peter
Jan 22 at 10:43
$begingroup$
Without a calculator, you probably can only sucessfully determine the result, if the number has very small prime factors.
$endgroup$
– Peter
Jan 22 at 10:43
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The method of prime factorization is correct, but inefficient. For example,
$234525482759285025987250295345695702224252525239458250845205825092502520592$ is rather hard to factor, but it is quite easy to check that it is divisible by $2^4$ but not by $2^5$.
answered Jan 21 at 3:05
Robert IsraelRobert Israel
326k23215469
$endgroup$
add a comment |
$begingroup$
The method of prime factorization is correct, as shown through your first example. The second example you have cited is wrong. $2$ does not divide $3^{9} cdot 5^{5} = 61509375$ because there is no even number in the prime factorization.
answered Jan 21 at 2:54
Ekesh KumarEkesh Kumar
1,04928
$endgroup$
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3081432%2fhighest-power-of-a-number-that-divides-a-larger-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The method of prime factorization is correct, but inefficient. For example,
$234525482759285025987250295345695702224252525239458250845205825092502520592$ is rather hard to factor, but it is quite easy to check that it is divisible by $2^4$ but not by $2^5$.
answered Jan 21 at 3:05
Robert IsraelRobert Israel
326k23215469
$endgroup$
add a comment |
$begingroup$
The method of prime factorization is correct, but inefficient. For example,
$234525482759285025987250295345695702224252525239458250845205825092502520592$ is rather hard to factor, but it is quite easy to check that it is divisible by $2^4$ but not by $2^5$.
answered Jan 21 at 3:05
Robert IsraelRobert Israel
326k23215469
$endgroup$
add a comment |
$begingroup$
The method of prime factorization is correct, but inefficient. For example,
$234525482759285025987250295345695702224252525239458250845205825092502520592$ is rather hard to factor, but it is quite easy to check that it is divisible by $2^4$ but not by $2^5$.
answered Jan 21 at 3:05
Robert IsraelRobert Israel
326k23215469
$endgroup$
The method of prime factorization is correct, but inefficient. For example,
$234525482759285025987250295345695702224252525239458250845205825092502520592$ is rather hard to factor, but it is quite easy to check that it is divisible by $2^4$ but not by $2^5$.
answered Jan 21 at 3:05
Robert IsraelRobert Israel
326k23215469
answered Jan 21 at 3:05
Robert IsraelRobert Israel
326k23215469
answered Jan 21 at 3:05
Robert IsraelRobert Israel
326k23215469
answered Jan 21 at 3:05
Robert IsraelRobert Israel
326k23215469
326k23215469
add a comment |
add a comment |
$begingroup$
The method of prime factorization is correct, as shown through your first example. The second example you have cited is wrong. $2$ does not divide $3^{9} cdot 5^{5} = 61509375$ because there is no even number in the prime factorization.
answered Jan 21 at 2:54
Ekesh KumarEkesh Kumar
1,04928
$endgroup$
add a comment |
$begingroup$
The method of prime factorization is correct, as shown through your first example. The second example you have cited is wrong. $2$ does not divide $3^{9} cdot 5^{5} = 61509375$ because there is no even number in the prime factorization.
answered Jan 21 at 2:54
Ekesh KumarEkesh Kumar
1,04928
$endgroup$
add a comment |
$begingroup$
The method of prime factorization is correct, as shown through your first example. The second example you have cited is wrong. $2$ does not divide $3^{9} cdot 5^{5} = 61509375$ because there is no even number in the prime factorization.
answered Jan 21 at 2:54
Ekesh KumarEkesh Kumar
1,04928
$endgroup$
The method of prime factorization is correct, as shown through your first example. The second example you have cited is wrong. $2$ does not divide $3^{9} cdot 5^{5} = 61509375$ because there is no even number in the prime factorization.
answered Jan 21 at 2:54
Ekesh KumarEkesh Kumar
1,04928
answered Jan 21 at 2:54
Ekesh KumarEkesh Kumar
1,04928
answered Jan 21 at 2:54
Ekesh KumarEkesh Kumar
1,04928
answered Jan 21 at 2:54
Ekesh KumarEkesh Kumar
1,04928
1,04928
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3081432%2fhighest-power-of-a-number-that-divides-a-larger-number%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
$begingroup$
If you know a prime factor, it can be efficiently determined which exponent in the prime factorization belongs to it by repeated division. But to determine the maximum exponent is not significantly easier than integer factorization: In particular , no efficient method is known to decide whether a given number is squarefree.
$endgroup$
– Peter
Jan 21 at 11:54
$begingroup$
So as a general case whenever one is to find max possible power of a given number that divides a very large number one should only eliminate the prime factorized version of the large number to get integral solution rather than going for mixed fraction one?
$endgroup$
– Yash Panchal
Jan 21 at 15:24
$begingroup$
In practice, I would partially factor the number by trial division upto , lets say, $10^9$. If the number is not too large, more advanced methods can be applied. If the number cannot be completely factored in a reasonable time, we cannot determine the largest exponent for sure. But it is very likely that the number (when not especially constructed) is not divisible by the square of a prime larger than $10^9$, so we can quite safely assume that the partial factorization reveals the correct result.
$endgroup$
– Peter
Jan 22 at 10:40
$begingroup$
Without a calculator, you probably can only sucessfully determine the result, if the number has very small prime factors.
$endgroup$
– Peter
Jan 22 at 10:43