Dtjytyk

Why Is Death Allowed In the Matrix?

Arthur Somervell: 1000 Exercises - Meaning of this notation

Show that if two triangles built on parallel lines, with equal bases have the same perimeter only if they are congruent.

Is it tax fraud for an individual to declare non-taxable revenue as taxable income? (US tax laws)

Can a Warlock become Neutral Good?

In Japanese, what’s the difference between “Tonari ni” (となりに) and “Tsugi” (つぎ)? When would you use one over the other?

Approximately how much travel time was saved by the opening of the Suez Canal in 1869?

Can I ask the recruiters in my resume to put the reason why I am rejected?

What are the differences between the usage of 'it' and 'they'?

How can bays and straits be determined in a procedurally generated map?

How does strength of boric acid solution increase in presence of salicylic acid?

Email Account under attack (really) - anything I can do?

Dragon forelimb placement

Font hinting is lost in Chrome-like browsers (for some languages )

How do we improve the relationship with a client software team that performs poorly and is becoming less collaborative?

TGV timetables / schedules?

Why don't electron-positron collisions release infinite energy?

I’m planning on buying a laser printer but concerned about the life cycle of toner in the machine

Risk of getting Chronic Wasting Disease (CWD) in the United States?

Theorem, big Paralist and Amsart

How is it possible to have an ability score that is less than 3?

A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?

Maximum likelihood parameters deviate from posterior distributions

How do I create uniquely male characters?

Find the greatest integer $k$ for which $1991^k$ divides $1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$

A couple of problems involving divisibility and congruencefor $n=x^2+3y^2$ , $n=prod p^{a(p)}$ , $a(p)$ is even for all $p equiv 2 pmod 3$ where $p$ is primeProve the fractions aren't integersInfinite set of positive integers such that the greatest common divisor of any two distinct numbers in $B$ is $p$Find all integer values of $x$, for $3^{x}equiv 18pmod{99}$Prove that an integer which divides $p^t$ must equal $p^k$ for some k, $1leq kleq t$Prove that there is no positive integer s.t. $1000^m-1$ divides $1396^m-1$prove that 15 divides $n^7+2n^5+4n^3+8n$ for any integer nWhat is the remainder when $ 6^{65} $ is divided by 80?Find primes $p$, for which the $x^2 equiv 7 pmod{p}$ has a solution

5

3

$begingroup$

Find the greatest integer $k$ for which $1991^k$ divides $$1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$$

It is easy to see that $k geq 1$ as $1990 equiv -1$ and $1992 equiv 1 pmod{1991}$
Also, I thought that perhaps as $1991$ is the product of two distinct primes, it would be worth looking at small values of $(pq)^k||(pq-1)^{{pq}^{pq+1}}+(pq+1)^{{pq}^{pq-1}}$ for primes $p$ and $q$. Any help would be really appreciated.

number-theory elementary-number-theory divisibility

share|cite|improve this question

edited May 14 '13 at 6:37

nbubis

27.4k552110

asked May 14 '13 at 6:25

John MartyJohn Marty

2,0141137

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  is it $1990^{left( 1991^{1992} right)}$ or $left( 1990^{1991} right)^{1992}$
  $endgroup$
  – DanZimm
  May 14 '13 at 6:41
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm pretty sure it's the former. But I'm not certain. This was the problem as I found it. I think it's from an IMO shortlist.
  $endgroup$
  – John Marty
  May 14 '13 at 6:51
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The existing answers show $k$ can be at least $1991$. I haven't followed the link to the detail of the "Lifting the Exponent Lemma", but do we know there is no greater value for $k$?
  $endgroup$
  – Mark Hurd
  Oct 9 '13 at 16:00
  

  
  
  
  

add a comment | 

5

3

$begingroup$

Find the greatest integer $k$ for which $1991^k$ divides $$1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$$

It is easy to see that $k geq 1$ as $1990 equiv -1$ and $1992 equiv 1 pmod{1991}$
Also, I thought that perhaps as $1991$ is the product of two distinct primes, it would be worth looking at small values of $(pq)^k||(pq-1)^{{pq}^{pq+1}}+(pq+1)^{{pq}^{pq-1}}$ for primes $p$ and $q$. Any help would be really appreciated.

number-theory elementary-number-theory divisibility

share|cite|improve this question

edited May 14 '13 at 6:37

nbubis

27.4k552110

asked May 14 '13 at 6:25

John MartyJohn Marty

2,0141137

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  is it $1990^{left( 1991^{1992} right)}$ or $left( 1990^{1991} right)^{1992}$
  $endgroup$
  – DanZimm
  May 14 '13 at 6:41
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm pretty sure it's the former. But I'm not certain. This was the problem as I found it. I think it's from an IMO shortlist.
  $endgroup$
  – John Marty
  May 14 '13 at 6:51
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The existing answers show $k$ can be at least $1991$. I haven't followed the link to the detail of the "Lifting the Exponent Lemma", but do we know there is no greater value for $k$?
  $endgroup$
  – Mark Hurd
  Oct 9 '13 at 16:00
  

  
  
  
  

add a comment | 

$begingroup$

Find the greatest integer $k$ for which $1991^k$ divides $$1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$$

It is easy to see that $k geq 1$ as $1990 equiv -1$ and $1992 equiv 1 pmod{1991}$
Also, I thought that perhaps as $1991$ is the product of two distinct primes, it would be worth looking at small values of $(pq)^k||(pq-1)^{{pq}^{pq+1}}+(pq+1)^{{pq}^{pq-1}}$ for primes $p$ and $q$. Any help would be really appreciated.

number-theory elementary-number-theory divisibility

share|cite|improve this question

edited May 14 '13 at 6:37

nbubis

27.4k552110

asked May 14 '13 at 6:25

John MartyJohn Marty

2,0141137

$endgroup$

share|cite|improve this question

edited May 14 '13 at 6:37

nbubis

27.4k552110

asked May 14 '13 at 6:25

John MartyJohn Marty

2,0141137

share|cite|improve this question

edited May 14 '13 at 6:37

nbubis

27.4k552110

asked May 14 '13 at 6:25

John MartyJohn Marty

2,0141137

edited May 14 '13 at 6:37

nbubis

27.4k552110

edited May 14 '13 at 6:37

nbubis

27.4k552110

asked May 14 '13 at 6:25

John MartyJohn Marty

2,0141137

asked May 14 '13 at 6:25

John MartyJohn Marty

2,0141137

2 Answers
2

active

oldest

votes

3

$begingroup$

I shall prove a more general result: Let $n>1$ be an odd positive integer. Then $n^n |[(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}]$.

Proof:
begin{align}
(n-1)^{n^2}+(n+1)=sum_{i=0}^{n^2}{binom{n^2}{i}(-1)^{n^2-i}n^i}+(n+1) & equiv binom{n^2}{1}n-1+(n+1) pmod{n^2}\
& equiv n pmod{n^2}
end{align}

Now applying Lifting the Exponent Lemma on each prime factor of $n$, we have $n^n |[(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}]$.

For your special case, $k=1991$.

share|cite|improve this answer

answered May 14 '13 at 7:02

Ivan LohIvan Loh

15.7k23251

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  (+1) For Lifting the exponent lemma. This seems pretty interesting. It can be used in Olympiad without mentioning the proof right?
  $endgroup$
  – Inceptio
  May 14 '13 at 7:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Inceptio yes. In this case, one would write $n=prod_{i=1}^{m}{p_i^{a_i}}$, then $v_{p_i}((n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}) =v_{p_i}((n-1)^{n^2}+(n+1))+v_{p_i}(n^{n-1}) =v_{p_i}(n^n)$
  $endgroup$
  – Ivan Loh
  May 14 '13 at 7:14
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm guessing $v_p(x^n+y^n)=v_p(x+y)+v_p(n)$ has been used here.
  $endgroup$
  – Inceptio
  May 14 '13 at 7:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Inceptio Indeed. Of course that requires the exponent to be odd, which is indeed the case here.
  $endgroup$
  – Ivan Loh
  May 14 '13 at 7:40
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The "lifting the exponent lemma" link is dead.
  $endgroup$
  – Mario Carneiro
  Apr 2 '15 at 6:08
  

  
  
  
  

add a comment | 

3

$begingroup$

Let $a=1991$, and let $$b=(a-1)^{ a^{a+1} } + (a+1)^{ a^{a-1} }$$

The goal is to compute $nu_{a}(b)$. To do so, we will evaluate $b$ modulo $a^{a+1}$.

Applying binomial expansions, $$bequiv (-1)^{a^{a+1}} + 1 + a^{a-1} amod{a^{a+1}}$$ (because all the higher order terms vanish).

Since $a^{a+1}$ is odd, this simplifies to $$b equiv a^amod{a^{a+1}}$$
Therefore, $nu_{a}(b)=a$. To rephrase in the terminology of your question, $k=1991$.

share|cite|improve this answer

answered May 14 '13 at 7:00

pre-kidneypre-kidney

12.9k1850

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Your wrote: "because all the higher order terms vanish". Do you have a proof of that?
  $endgroup$
  – Bill Dubuque
  Mar 20 at 1:27
  

  
  
  
  

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
});


}
});

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

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f391107%2ffind-the-greatest-integer-k-for-which-1991k-divides-1990199119921%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

I shall prove a more general result: Let $n>1$ be an odd positive integer. Then $n^n |[(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}]$.

Proof:
begin{align}
(n-1)^{n^2}+(n+1)=sum_{i=0}^{n^2}{binom{n^2}{i}(-1)^{n^2-i}n^i}+(n+1) & equiv binom{n^2}{1}n-1+(n+1) pmod{n^2}\
& equiv n pmod{n^2}
end{align}

Now applying Lifting the Exponent Lemma on each prime factor of $n$, we have $n^n |[(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}]$.

For your special case, $k=1991$.

share|cite|improve this answer

answered May 14 '13 at 7:02

Ivan LohIvan Loh

15.7k23251

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  (+1) For Lifting the exponent lemma. This seems pretty interesting. It can be used in Olympiad without mentioning the proof right?
  $endgroup$
  – Inceptio
  May 14 '13 at 7:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Inceptio yes. In this case, one would write $n=prod_{i=1}^{m}{p_i^{a_i}}$, then $v_{p_i}((n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}) =v_{p_i}((n-1)^{n^2}+(n+1))+v_{p_i}(n^{n-1}) =v_{p_i}(n^n)$
  $endgroup$
  – Ivan Loh
  May 14 '13 at 7:14
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm guessing $v_p(x^n+y^n)=v_p(x+y)+v_p(n)$ has been used here.
  $endgroup$
  – Inceptio
  May 14 '13 at 7:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Inceptio Indeed. Of course that requires the exponent to be odd, which is indeed the case here.
  $endgroup$
  – Ivan Loh
  May 14 '13 at 7:40
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The "lifting the exponent lemma" link is dead.
  $endgroup$
  – Mario Carneiro
  Apr 2 '15 at 6:08
  

  
  
  
  

add a comment | 

3

$begingroup$

I shall prove a more general result: Let $n>1$ be an odd positive integer. Then $n^n |[(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}]$.

Proof:
begin{align}
(n-1)^{n^2}+(n+1)=sum_{i=0}^{n^2}{binom{n^2}{i}(-1)^{n^2-i}n^i}+(n+1) & equiv binom{n^2}{1}n-1+(n+1) pmod{n^2}\
& equiv n pmod{n^2}
end{align}

Now applying Lifting the Exponent Lemma on each prime factor of $n$, we have $n^n |[(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}]$.

For your special case, $k=1991$.

share|cite|improve this answer

answered May 14 '13 at 7:02

Ivan LohIvan Loh

15.7k23251

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  (+1) For Lifting the exponent lemma. This seems pretty interesting. It can be used in Olympiad without mentioning the proof right?
  $endgroup$
  – Inceptio
  May 14 '13 at 7:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Inceptio yes. In this case, one would write $n=prod_{i=1}^{m}{p_i^{a_i}}$, then $v_{p_i}((n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}) =v_{p_i}((n-1)^{n^2}+(n+1))+v_{p_i}(n^{n-1}) =v_{p_i}(n^n)$
  $endgroup$
  – Ivan Loh
  May 14 '13 at 7:14
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm guessing $v_p(x^n+y^n)=v_p(x+y)+v_p(n)$ has been used here.
  $endgroup$
  – Inceptio
  May 14 '13 at 7:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Inceptio Indeed. Of course that requires the exponent to be odd, which is indeed the case here.
  $endgroup$
  – Ivan Loh
  May 14 '13 at 7:40
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The "lifting the exponent lemma" link is dead.
  $endgroup$
  – Mario Carneiro
  Apr 2 '15 at 6:08
  

  
  
  
  

add a comment | 

$begingroup$

I shall prove a more general result: Let $n>1$ be an odd positive integer. Then $n^n |[(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}]$.

Proof:
begin{align}
(n-1)^{n^2}+(n+1)=sum_{i=0}^{n^2}{binom{n^2}{i}(-1)^{n^2-i}n^i}+(n+1) & equiv binom{n^2}{1}n-1+(n+1) pmod{n^2}\
& equiv n pmod{n^2}
end{align}

Now applying Lifting the Exponent Lemma on each prime factor of $n$, we have $n^n |[(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}]$.

For your special case, $k=1991$.

share|cite|improve this answer

answered May 14 '13 at 7:02

Ivan LohIvan Loh

15.7k23251

$endgroup$

share|cite|improve this answer

answered May 14 '13 at 7:02

Ivan LohIvan Loh

15.7k23251

answered May 14 '13 at 7:02

Ivan LohIvan Loh

15.7k23251

answered May 14 '13 at 7:02

Ivan LohIvan Loh

15.7k23251

3

$begingroup$

Let $a=1991$, and let $$b=(a-1)^{ a^{a+1} } + (a+1)^{ a^{a-1} }$$

The goal is to compute $nu_{a}(b)$. To do so, we will evaluate $b$ modulo $a^{a+1}$.

Applying binomial expansions, $$bequiv (-1)^{a^{a+1}} + 1 + a^{a-1} amod{a^{a+1}}$$ (because all the higher order terms vanish).

Since $a^{a+1}$ is odd, this simplifies to $$b equiv a^amod{a^{a+1}}$$
Therefore, $nu_{a}(b)=a$. To rephrase in the terminology of your question, $k=1991$.

share|cite|improve this answer

answered May 14 '13 at 7:00

pre-kidneypre-kidney

12.9k1850

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Your wrote: "because all the higher order terms vanish". Do you have a proof of that?
  $endgroup$
  – Bill Dubuque
  Mar 20 at 1:27
  

  
  
  
  

add a comment | 

3

$begingroup$

Let $a=1991$, and let $$b=(a-1)^{ a^{a+1} } + (a+1)^{ a^{a-1} }$$

The goal is to compute $nu_{a}(b)$. To do so, we will evaluate $b$ modulo $a^{a+1}$.

Applying binomial expansions, $$bequiv (-1)^{a^{a+1}} + 1 + a^{a-1} amod{a^{a+1}}$$ (because all the higher order terms vanish).

Since $a^{a+1}$ is odd, this simplifies to $$b equiv a^amod{a^{a+1}}$$
Therefore, $nu_{a}(b)=a$. To rephrase in the terminology of your question, $k=1991$.

share|cite|improve this answer

answered May 14 '13 at 7:00

pre-kidneypre-kidney

12.9k1850

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Your wrote: "because all the higher order terms vanish". Do you have a proof of that?
  $endgroup$
  – Bill Dubuque
  Mar 20 at 1:27
  

  
  
  
  

add a comment | 

$begingroup$

Let $a=1991$, and let $$b=(a-1)^{ a^{a+1} } + (a+1)^{ a^{a-1} }$$

The goal is to compute $nu_{a}(b)$. To do so, we will evaluate $b$ modulo $a^{a+1}$.

Applying binomial expansions, $$bequiv (-1)^{a^{a+1}} + 1 + a^{a-1} amod{a^{a+1}}$$ (because all the higher order terms vanish).

Since $a^{a+1}$ is odd, this simplifies to $$b equiv a^amod{a^{a+1}}$$
Therefore, $nu_{a}(b)=a$. To rephrase in the terminology of your question, $k=1991$.

share|cite|improve this answer

answered May 14 '13 at 7:00

pre-kidneypre-kidney

12.9k1850

$endgroup$

share|cite|improve this answer

answered May 14 '13 at 7:00

pre-kidneypre-kidney

12.9k1850

answered May 14 '13 at 7:00

pre-kidneypre-kidney

12.9k1850

answered May 14 '13 at 7:00

pre-kidneypre-kidney

12.9k1850