Find (a,n)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shobber

3498 posts

shobber

#1 h Mar 24, 2006, 11:48 AM • 9 Y

Y by Mgh, itslumi, ImSh95, centslordm, Adventure10, megarnie, son7, Mango247, Funcshun840

Find all positive integer pairs $(a,n)$ such that $\frac{(a+1)^n-a^n}{n}$ is an integer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Rust

5049 posts

Rust

#2 h Mar 24, 2006, 12:56 PM • 5 Y

Y by centslordm, Adventure10, ImSh95, son7, Mango247

$(a+1)^n=a^n (mod \ n) \Longrightarrow (a,n)=1,b^n=1(mod \ n)$ , were a(b-1)=1(mod n). It give algoritm:
If (c(n),n)=d>1 we have not trivial solutions b^d=1(mod n). If (b-1,n)=1, it give solutions a=1/(b-1) (mod n).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

frengo

28 posts

frengo

#3 h Mar 27, 2006, 10:19 AM • 5 Y

Y by centslordm, Adventure10, ImSh95, son7, Mango247

ehm...i don't understand;here is my solution:

at first, let's suppose $(a;n)=1$

take the smaller prime factor of $n$ and let's call it $p$ , with $n=p^ck$

so, it must be

$(a+1)^{p^ck}\equiv a^{p^ck}$ $(\mod p)$

by Fermat's theorem

$(a+1)^{k}\equiv a^{k}$ $(\mod p)$

$[(a+1)\cdot a^{-1}]^k\equiv 1$ $(\mod p)$

so the smaller number $x>0$ such that $[(a+1)\cdot a^{-1}]^x\equiv 1$ $(\mod p)$ is a divisor of $k$ .
we now also that that this number x is a divisor of $\phi(p)=p-1$ , but all divisors of $k$ are greater than $p$ and so $x=1$ .

$(a+1)\cdot a^{-1}\equiv 1$ $(\mod p)$

$a+1\equiv a$ $(\mod p)$

$1\equiv 0$ $(\mod p)$

so this smaller prime does'n't exist,and there can be only $n=1$ .
in fact, with $n=1$ we have solution for every $a$ .

it remain only the case of $(a;n)=d>0$

but in this case the numerator becomes $\equiv 1$ $(\mod d)$ and so it cannot be a multiple of $n$ .

the only solution are so $(a;1)$ for each $a\in\mathbb{N}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Omid Hatami

1275 posts

Omid Hatami

#4 h Mar 28, 2006, 7:30 AM • 19 Y

Y by AnArtist, e_plus_pi, MathPassionForever, mathsfun28, MONYmath10, A-Thought-Of-God, 554183, mo.s.k14142, Adventure10, ImSh95, son7, sabkx, Mango247, Mango247, Mango247, Rainmaker2627, ATM_, Nari_Tom, MS_asdfgzxcvb

Suppose $p$ is the smallest prime divisor of $n$ the $p|(a+1)^n-a^n\Rightarrow p|(a+1)-a=1$ . So contradiction proves that $n=1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

José

1828 posts

José

#5 h Apr 2, 2006, 9:45 PM • 4 Y

Y by Adventure10, ImSh95, son7, Mango247

Omid Hatami wrote:

Suppose $p$ is the smallest prime divisor of $n$ the $p|(a+1)^n-a^n\Rightarrow p|(a+1)-a=1$ . So contradiction proves that $n=1$

So simple and elegant, excellent!!!!!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

José

1828 posts

José

#6 h Apr 2, 2006, 10:16 PM • 4 Y

Y by Adventure10, ImSh95, son7, Mango247

Another thing... These three problems are the only 3 or there is another round in China TST?? And another question: These 3 problems are really difficult to solve, aren´t they?????? (as any China TST) or any high-school olympiad student can solve them?????

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

marko avila

521 posts

marko avila

#7 h Apr 3, 2006, 4:45 AM • 3 Y

Y by Adventure10, ImSh95, son7

dear omid :
I dont follow your solution could you put more details in?

p.s. your solution is very interesting.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dblues

203 posts

dblues

#8 h Apr 3, 2006, 5:32 PM • 19 Y

Y by madmathlover, AnArtist, e_plus_pi, MathPassionForever, MathBoy23, A-Thought-Of-God, Aimingformygoal, myh2910, Adventure10, Pratik12, ImSh95, son7, Mathlover_1, Quidditch, sabkx, Mango247, Marcos_Vinicius, vrondoS, and 1 other user

$p|(a+1)^n-a^n\Rightarrow p|(a+1)-a=1$ is definitely correct, but I think you have jumped too many steps Omid Hatami.

To see why this is correct, we first let $b$ be the unique inverse such that $ab\equiv 1 \pmod{p}$ . We have $(a+1)^n \equiv a^n \pmod{p}$ , and multiplying both sides by $b^n$ , we get $((a+1)b)^n \equiv 1 \pmod{p}$ . Letting $d$ be the order of $((a+1)b) \mod p$ , we have $d\mid n$ . Yet, by Fermat's Little Theorem, we have $((a+1)b)^{p-1}\equiv 1 \pmod{p}$ , so $d\mid p-1 \Rightarrow d < p \Rightarrow \gcd (d,n)=1$ , due to the definition of $p$ as the smallest prime divisor of $n$ . Thus $d=1$ , implying that $(a+1) \equiv a \pmod{p}$ , which is the contradiction we want.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

behzad

55 posts

behzad

#9 h Apr 6, 2006, 8:33 PM • 7 Y

Y by rmtf1111, Adventure10, ImSh95, son7, Mathlover_1, Mango247, ryanbear

obviously $n$ isn't even. Let $p$ be the smallest prime divisor of $n$ .and let $g$ be a primitive root modulo $p$ . Let $a+1\equiv g^k,a\equiv g^l \pmod{p}$ so ve have :
$g^{kn} \equiv g^{ln}\pmod{p}$ so $p-1|n(k-l)$ so $p-1|k-l$ .so $p|g^k-g^l$ so $p|(a+1)-a$ so $p=1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jin

383 posts

jin

#10 h Apr 7, 2006, 6:13 AM • 4 Y

Y by Adventure10, ImSh95, son7, Mango247

In fact there are 8 round in the China TST and in the first six round every problem is worth 7 points and in the last 2 days every one 21.So when we say China TST,we often means the last two days.And this 3 problem is the first round of 8!
First two problems is very easy but I think no one can complete the third one in the exam.
This 3 problems is from Zuming Feng,the IMO team leader of USA in 2005.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

José

1828 posts

José

#11 h Apr 7, 2006, 9:24 PM • 4 Y

Y by Adventure10, ImSh95, son7, Mango247

I see jin... and what's the difficulty of this problem????? (really hard?)Is it like what number of an IMO problem?????? or it is easier like an IMO problem?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jin

383 posts

jin

#12 h Apr 8, 2006, 2:08 PM • 4 Y

Y by Adventure10, ImSh95, son7, Mango247

This one?the second one is really easy, I think almost every one in the exam can solute it.
But I made a very silly mistake(forgot n=1)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

spoudyal

143 posts

spoudyal

#13 h Apr 9, 2006, 10:48 PM • 2 Y

Y by Adventure10, ImSh95

Hmmm ... I am really new to number theory and I can not understand most of what you guys did and when I can I am not always able to figure out how you got there so I tried to go for it myself. Anyways, this is what I got and please tell me where any errors occur.

((a+1)^n - a^n) / n == 0 (mod m) (== means congruent to)

multiply both sides of congrunce by n to get

(a+1)^n - a^n == 0 (mod m)

now we can add a^n to both sides to produce

(a+1)^n == a^n (mod m)

I think that this means n must equal 1, therefore we say

(a+1) == a (mod m)

substracting a from both sides we see that

1 == 0 (mod m) which is the same as saying (1-0)/m is an integer

this is only true if m =1 (we are dealing with only positive integers in this problem)

so going back to our original equation we plug in n=1 and m=1 for the integer our equation must yield

((a+1)^1 - a^1)/1 = 1 => a+1 - a = 1 => 1=1
since this is true for any 'a' our solution is

(a,1)

Thank you for any help you can provide me with!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dblues

203 posts

dblues

#14 h Apr 10, 2006, 7:34 AM • 3 Y

Y by Adventure10, ImSh95, Mango247

Here are some of my comments on your solution.

From the first line of your solution, you have defined $m$ as some divisor of $\frac{(a+1)^n-a^n}{n}$ . Even if you eventually show that $m=1$ , you have only shown that $\frac{(a+1)^n-a^n}{n}$ is indeed an integer, which was what you have assumed right from the start. For this problem, you do not want to investigate the divisors of $\frac{(a+1)^n-a^n}{n}$ ; rather, you want to investigate the divisors of $n$ . So you should just let your $m$ be any divisor of $n$ , and what you want to show in the end is that this arbitrary divisor of $n$ has to be $1$ . Your first line of the solution should just be ${(a+1)^n-a^n \equiv 0 \pmod{m}}$ , where $m\mid n$ .

Next, we arrive at your step of $(a+1)^n \equiv a^n \pmod{m}$ implying $(a+1) \equiv a \pmod{m}$ . Though this is true in reality, you did not provide any justification to this step.

Remember, you want to show that $m=1$ in the end, so we want to assume $m>1$ and derive a contradiction. Now, if we know $m>1$ , definitely, $m$ must have at least one prime divisor. The trick we use here is to let $p$ be the smallest such prime divisor of $m$ to derive the contradiction we want. Now we have $(a+1)^n \equiv a^n \pmod{p}$ .

We notice that $p$ does not divide both $(a+1)$ and $a$ (Why? Look back at our original problem..), so there must exist a unique inverse of $a$ (Why?). letting $b$ be that unique inverse, we have $ab \equiv 1 \pmod{p}$ by definition. Thus, back to our congruence $(a+1)^n \equiv a^n \pmod{p}$ , by multiplying both sides by $b^n$ , we get $((a+1)b)^n \equiv 1 \pmod{p}$ .

For the rest of the solution, refer to my previous post, or Omid Hatami's solution (behzad's solution uses a slightly different approach, but it is still similar in idea). Recall that if $d$ is the order of $x \mod y$ , then $d$ is the smallest positive integer such that $x^d \equiv 1 \pmod{y}$ . If we have $x^M \equiv 1 \pmod{y}$ , then we must necessarily have $d\mid M$ . (Why? Try convincing yourself on this first.)

I hope you can understand better now.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

spoudyal

143 posts

spoudyal

#15 h Apr 10, 2006, 10:34 PM • 2 Y

Y by Adventure10, Mango247

I really understand the solutions now. Using be was pure genius and I understand why m=1 by the contradiction. Thanks for all the help dblues!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#63 h Apr 13, 2023, 10:05 PM

Y by

The answer is $(1, a)$ only. The idea is to pick a minimal prime $p \mid n$ , such that $a+1 \equiv a \pmod p$ for order reasons. This implies $p=1$ , thus only $n=1$ can work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4175 posts

john0512

#64 h Jul 25, 2023, 12:09 AM

Y by

The condition is essentially just $(a+1)^n\equiv a^n\pmod{n}$
Case 1: $n$ does not divide $a$ . Then, let $p$ be the smallest positive integer that divides $n$ but not $a$ . Then, we have $(\frac{a+1}{a})^n\equiv 1\pmod{p}.$ Therefore, the order of $(a+1)/a$ mod $p$ divides $n$ . However, this is smaller than $p$ , and by definition, all divisors of $n$ smaller than $p$ are also divisors of $a$ . Thus, unless the order of $(a+1)/a$ is 1 (i.e. $a+1\equiv a\pmod{n}$ so $n=1$ , contradiction since $n$ does not divide $a$ ), $a$ and $n$ are not relatively prime, since this order divides both of them. Suppose $q\mid a$ and $q\mid n$ . Then, taking $(a+1)^n\equiv a^n\pmod n$ mod $q$ reveals that $1\equiv 0\pmod{q},$ contradiction.

Case 2: $n$ divides $a$ . Then, this is just $(a+1)^n\equiv a^n\pmod n$ $1\equiv 0\pmod{n},$ so $n=1$ . Thus, the answer is $n=1$ and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

minusonetwelth

225 posts

minusonetwelth

#65 h Aug 15, 2023, 12:04 PM

Y by

Some months later solve:

Clearly, $n=1$ and $a\in\mathbb{Z}^+$ work. Therefore, assume $n>1$ from now on. Let $p$ be the smallest prime divisor of $n$ , so that
$(a+1)^n\equiv a^n\mod p$ Let $g$ be a primitive root mod $p$ , and let $0\le\alpha,\beta\le p-2$ such that $g^{\alpha n}\equiv(a+1)^n\equiv a^n\equiv g^{\beta n}\mod p$ . We get
$g^{n(\alpha-\beta)}\equiv 1\mod p,$ meaning $p-1\mid n(\alpha-\beta)$ . However, as $p$ is the smallest prime dividing $n$ , $\gcd(p-1,n)=1$ , so $p-1\mid \alpha-\beta$ . As $0\le\alpha,\beta\le p-2$ we must have $\alpha=\beta$ . We get get $a+1\equiv g^{\alpha}\equiv g^{\beta}\equiv a\mod p$ , implying $0\equiv 1\mod p$ , which is impossible, so we have no more solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

F10tothepowerof34

195 posts

F10tothepowerof34

#66 h Sep 27, 2023, 4:27 PM

Y by

Here's an attempt at a different solution

Let $a=\prod_{i=1}^{k}p_i^{\alpha_i}$ . Now using this observe that $(a+1)^n=\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)^n\equiv 1\pmod {p_1}\text{ thus }\operatorname{ord}{p_1}(a+1)=\operatorname{ord}{p_1}\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)=n\mid p_1-1\Longleftrightarrow p_1\equiv1\pmod n$ $\text{ Furthermore } (a+1)^n=\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)^n\equiv1\pmod {p_2}\text{ thus }\operatorname{ord}{p_2}(a+1)=\operatorname{ord}{p_2}\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)=n\mid p_2-1\Longleftrightarrow p_2\equiv1\pmod n$ $\vdots$ $\text{ Now } (a+1)^n=\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)^n\equiv1\pmod {p_k}\text{ thus }\operatorname{ord}{p_k}(a+1)=\operatorname{ord}{p_k}\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)=n\mid p_k-1\Longleftrightarrow p_k\equiv1\pmod n$ $\text{ Using all these together we obtain that }\prod_{i=1}^{k}p_i^{\alpha_i}\equiv1\pmod n$ Moreover notice that our original condition is equivalent to $\frac{(a+1)^n-a^n}{n}\Longleftrightarrow(a+1)^n-a^n\equiv0\pmod n$
However $(a+1)^n-a^n=\left(\prod_{i=1}^{k}p_i^{\alpha_i}+1\right)^n-\left(\prod_{i=1}^{k}p_i^{\alpha_i}\right)^n\equiv (1+1)^n-1^n\equiv 2^n-1\pmod n$
Therefore the condition transforms into $2^n-1\equiv0\pmod n\Longleftrightarrow 2^n\equiv 1\pmod n$

Claim: $2^n\equiv 1\pmod n$ if and only if $n=1$
Proof:
Notice that if $n\equiv 0\pmod 2$ we have that $2^n-1\equiv 1\pmod 2\text{ while }n\equiv0\pmod 2$ which is clearly a contradiction, thus $n\equiv 1\pmod 2\Longleftrightarrow\gcd(2,n)=1$
Now since $\gcd(2,n)=1$ we have that $2^n\equiv1\pmod n\Longrightarrow\operatorname{ord}_{n}(2)=n\mid\phi(n)\Longrightarrow n\mid\phi(n)\Longleftrightarrow\frac{\phi(n)}{n}\in\mathbb{Z}$
Furthermore let $n=\prod_{i=1}^{t}q_i^{\beta_i}$ and recall that $\frac{\phi(n)}{n}=\frac{\phi(\operatorname{rad} (n))}{\operatorname{rad}(n)}$ thus $\frac{\phi(n)}{n}=\frac{\phi\left(\prod_{i=1}^{t}q_i^{\beta_i}\right)}{\prod_{i=1}^{t}q_i^{\beta_i}}=\frac{\phi\left(\operatorname{rad} \left(\prod_{i=1}^{t}q_i^{\beta_i}\right)\right)}{\operatorname{rad}\left(\prod_{i=1}^{t}q_i^{\beta_i}\right)}=\frac{\phi\left(\prod_{i=1}^{t}q_i\right)}{\prod_{i=1}^{t}q_i}$
Furthermore since $\gcd(q_1,q_2,\dots,q_t)=1$ we have that $\phi\left(\prod_{i=1}^{t}q_i\right)=\prod_{i=1}^{t}\phi(q_i)=\prod_{i=1}^{t}q_i-1$
Therefore we need to have $\frac{\prod_{i=1}^{t}q_i-1}{\prod_{i=1}^{t}q_i}\in\mathbb{Z}$ which is clearly only the case when $n=1$ $\square$ .

So plugging in $n=1$ into our original equation yields $\frac{a+1-a}{1}=1$ which is clearly an integer. Thus $(a,n)=(a,1)$ for any integer $a$ is the only solution $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mannshah1211

651 posts

mannshah1211

#67 h Jan 20, 2024, 11:43 AM

Y by

I claim the only solutions are $(a, n) = (x, 1).$ Henceforth assume $n > 1.$

Claim: $\gcd(a, n) = \gcd(a + 1, n) = 1$
Proof. Let $\gcd(a, n) = d > 1,$ then we have $d \mid a^n,$ but we must have $d \nmid a + 1,$ since if $d \mid a + 1,$ $d \mid \gcd(a, a + 1) = 1,$ contradiction. So, $d \nmid (a + 1)^n - a^n,$ but $d \mid n \mid (a + 1)^n - a^n,$ contradiction. Similarly, $\gcd(a + 1, n) = 1.$

Thus, there exist inverse of $a$ modulo $n$ , so $(a + 1)^n \equiv a^n \pmod{n} \implies \left(\frac{a + 1}{a}\right)^n \equiv 1 \pmod{n},$ let $\frac{a + 1}{a} \equiv a^{*} \pmod{n},$ so let $p$ be the smallest prime divisor of $n$ , this gives that $\mathrm{ord}_p(a^{*}) \mid \gcd(n, p - 1) = 1,$ so $a^{*} \equiv 1 \pmod{p},$ so $\frac{a + 1}{a} \equiv 1 \pmod{p},$ a contradiction, since $p > 1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lelouchvigeo

174 posts

lelouchvigeo

#68 h Jan 20, 2024, 4:04 PM

Y by

Had solved this way back. Felt like posting now
Its clear that $\gcd(a, n) = 1$ .Its also clear that $n$ is odd. Let $p$ be the minimal prime dividng $n$ .
$(a+1)^n \equiv a^n (mod p)$ . But we also have that, $(a+1)^{p-1} \equiv a^{p-1} (mod p)$ . Its easy to see that due to this $p=2$ . A contradiction.
This implies $n=1$ . Thus $(a,1)$ is the only solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

942 posts

AshAuktober

#69 h Jan 20, 2024, 4:41 PM

Y by

We claim the solutions are $(a, 1)$ for all positive integers $a$ .
Note that the condition reduces to $(a+1)^n \equiv a^n$ mod $n$ .
Assume that $n > 1$ . In this case, let $p$ be the smallest prime divisor of $n$ .
Clearly $(a+1)^n \equiv a^n$ mod $p$ .
Also observer that $gcd(a, n) = gcd(a+1, n) = 1$ , so from Fermat's Little Theorem, $(a+1)^{p-1} \equiv a^{p-1}$ mod $p$ .
Combining these two and applying the Euclidean Algorithm, we get
$a^{gcd(p-1, n)} \equiv (a+1)^{gcd(p-1, n)} \text{ mod } p \implies a+1 \equiv a \text{ mod } p \implies p = 1$
But $p$ is prime so this is not possible. Therefore $n = 1$ .
But it is clearly visible that any $a$ works for $n = 1$ , so we have our solutions. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MagicalToaster53

159 posts

MagicalToaster53

#70 h Feb 5, 2024, 12:33 AM

Y by

I claim that all solutions of the form $\boxed{(a, 1)}$ where $a \in \mathbb{Z}^+$ .

Assume then $n \neq 1$ , as $n = 1$ is trivial. Let $p$ be the smallest prime dividing $n$ . Also (as the inverse exists) let $b$ denote the inverse of $a + 1$ . Then we have $(a + 1)b \equiv 1 \pmod p \implies (a + 1)^nb^n \equiv 1 \pmod p$ , so that $\implies o((a + 1)b)_p \mid p - 1 \text{ and } o((a + 1)b)_p \mid n \implies o((a + 1)b)_p \mid \gcd(n, p - 1).$ However as $p$ is the smallest prime that divides $n$ , we must have $\gcd(n, p - 1) = 1$ , so that $o((a + 1)b)_p = 1$ . Therefore if $b$ is to be $a^{-1}$ , then $a + 1 \equiv a \pmod p \implies 1 \equiv 0 \pmod p$ , which is a contradiction. Hence $\boxed{n = 1}$ is the only such solution. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

186 posts

de-Kirschbaum

#72 h Jun 16, 2024, 5:11 PM

Y by

Here's a worse solution than the other ones in this thread.

Note that if $n=1$ then all $a$ works, so suppose $n>1$ . Then $(a+1)^n \equiv a^n \mod{n} \implies \gcd(a,n)=1$ . Note that $2 \nmid n$ since $2^n-1^n \equiv 1 \mod{2}$ .

Denote $s=\frac{a+1}{a}$ . Thus $(\frac{a+1}{a})^n \equiv 1 \mod{n} \implies \mathrm{ord}_n(s) \mid n$ . Suppose that order is not 1. Then for any $p^k \mid n$ we have that $s^{\mathrm{ord}_n(s)} \equiv 1 \mod{p^k}$ so $\mathrm{ord}_{p^k}(s)|\mathrm{ord}_n(s)|n$ . Now note that $s^{\mathrm{ord}_{p^k}(s)} \equiv 1 \mod{p^k} \implies s^{\mathrm{ord}_{p^k}(s)} \equiv 1 \mod{p}$ . So $\mathrm{ord}_{p^k}(s) \mid n, \mathrm{ord}_{p^k}(s) \mid p-1 \textrm{ or } p-1 \mid \mathrm{ord}_{p^k}(s)$ . If $\mathrm{ord}_{p^k}(s) \neq 1$ then it either contains non-1 factors of $p-1$ or contains the entirety of $p-1$ which isn't $1$ . Either way, it cannot divide $n$ since $\gcd(n, p-1)=1$ . Thus $\mathrm{ord}_{p^k}(s)=1$ which implies $\frac{a+1}{a} \equiv 1 \mod{p^k}$ for all $p^k \mid n$ , by CRT that implies $\frac{a+1}{a} \equiv 1 \mod{n} \implies n=1$ . A contradiction, thus $n>1$ has no solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ATGY

2502 posts

ATGY

#73 h Jun 21, 2024, 6:28 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

381 posts

alexanderhamilton124

#74 h Sep 14, 2024, 2:19 PM

Y by

The case $n = 1$ is trivially true, so assume $n \neq 1$ .

Let $p$ denote the smallest prime divisor of $n$ . Note that $p \mid (a + 1)^n - a^n \implies (a + 1)^n \equiv a^n \mod{p}$ . If $p \mid a + 1$ , then $p \nmid a$ , a contradiction. Similarly for $p \mid a, p \nmid a + 1$ , and of course $p$ can't divide both $a + 1, a$ since $\gcd(a + 1, a) = 1$ . Therefore, $p \nmid a, a + 1$ .

So, $\left(\frac{a + 1}{a}\right)^n \equiv 1\mod{p}$ Let $\frac{a + 1}{a} = \alpha$ . We have $\text{ord}_p(\alpha) \mid n$ , $\text{ord}_p(\alpha) \mid p - 1$ by Fermat's Little Theorem, so $\text{ord}_p(\alpha) \mid \gcd(n, p - 1)$ . Note that that $\gcd(n, p - 1) = 1$ , else we have a smaller prime divisor of $n$ than $p$ . So, $\alpha \equiv 1\mod{p} \implies a + 1 \equiv a \mod{p}$ , an obvious contradiction. Hence, we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

558 posts

cursed_tangent1434

#75 h Sep 21, 2024, 12:40 AM

Y by

We claim that the only pairs of solutions are $(a,n)=(m,1)$ for all positive integers $m$ . It is easy to see that all such pairs are indeed solutions. Now, we show that they are the only ones.

When $n>1$ and $n$ is even,
$2\mid n \mid (a+1)^n-a^n$ But it is clear that the right hand side is odd, which is a clear contradiction. Thus, any solution must have odd $n$ .

When $n>1$ and $n$ is odd, consider the smallest prime factor $p$ of $n$ . Clearly $p\nmid a,a+1$ since these are relatively prime. Further,
$\begin{align*} (a+1)^n &\equiv a^n \pmod{p}\\ \left(\frac{a+1}{a}\right)^n \equiv 1 \pmod{p} \end{align*}$ Thus, $\text{ord}_p\left(\frac{a+1}{a}\right)\mid n$ . Also, we know that $\text{ord}_p\left(\frac{a+1}{a}\right) \mid p-1$ by Fermat's Little Theorem. Now, $\text{ord}_p\left(\frac{a+1}{a}\right) \ne 1$ since this implies $a+1\equiv a \pmod{p}$ which is a contradiction. Thus, there exists a prime factor $q$ of $\text{ord}_p\left(\frac{a+1}{a}\right)$ . Since, $\text{ord}_p\left(\frac{a+1}{a}\right) \le p-1 < p$ it follows that $q<p$ but since $\text{ord}_p\left(\frac{a+1}{a}\right) \mid n$ , this implies that $q$ is a smalle prime factor of $n$ than $p$ . This is a clear contradiction! Thus, we have no solutions where $n>1$ as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

279 posts

peppapig_

#76 h Sep 26, 2024, 8:36 PM

Y by

I claim that the only solutions are $(a,1)$ for all positive integers $a$ . Clearly these work, since $1$ divides anything.

Now, I claim that $n$ cannot take any other values. First, note that $n$ cannot be even, as if $n$ is even, then one of $(a+1)^n$ and $a^n$ is even and the other is odd, making the difference odd and therefore not divisible by $2$ . This means that $n$ must be odd.

Assume that $n$ is not $1$ , and consider the smallest prime that divides $n$ , or $p$ . Notice that both $a+1$ and $a$ must be relatively prime to $p$ , or else one of $(a+1)^n$ and $a^n$ will be divisible by $p$ while the other is not. This makes the difference not divisible by $p$ , and therefore not divisible by $n$ . However, if both $a+1$ and $a$ are relatively prime to $p$ , modular inverses exist, so we can get that
$n\mid (a+1)^n-a^n \implies a^n\equiv (a+1)^n \mod p,$ $\implies \left(\frac{a+1}{a}\right)^n\equiv 1\mod p,$ which implies that the order of $\frac{a+1}{a}$ mod $p$ must divide into $n$ . However, notice that this order must divide $p-1$ (by FLT) and it cannot be $1$ , since $\frac{a+1}{a}$ is clearly not $1$ mod $p$ . This means that a number $\leq p-1$ and therefore $<p$ that is not $1$ divides into $n$ , implying that a prime smaller than $p$ must divide into $n$ . This is a clear contradiction to our assumption that $p$ was the smallest prime that divided $n$ , meaning that no primes $p$ can divide $n$ .

Therefore $n$ can only be $1$ , so our solutions of $(a,1)$ are the only possible solutions, which we proved worked. This finishes the problem.

This post has been edited 1 time. Last edited by peppapig_, Sep 26, 2024, 8:37 PM
Reason: <=p-1 not <=p

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

KevinYang2.71

409 posts

KevinYang2.71

#77 h Dec 20, 2024, 7:39 AM • 1 Y

Y by LostDreams

Only $n=1$ (and all $a$ ) works.

Suppose FTSOC $n>1$ and there exists $a$ such that $(a+1)^n\equiv a^n\pmod{n}$ . Clearly $a$ and $a+1$ must be relatively prime to $n$ so $(1+1/a)^n\equiv 1\pmod {n}$ . Let $p$ be the smallest prime factor of $n$ . Then $(1+1/a)^n\equiv 1\pmod{p}$ so $1+1/a\equiv 1\pmod{p}$ because $\gcd(p-1,\,n)=1$ , a contradiction. $\square$

This post has been edited 2 times. Last edited by KevinYang2.71, Dec 20, 2024, 7:40 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cherry265

15 posts

cherry265

#78 h Mar 21, 2025, 4:52 AM

Y by

edemafa wrote:

Here is a short solution.

*if $n$ is even no solution.

* if $n= p_1^{u_1}.p_2^{u_2}...p_n^{u_n}$ with $p_i$ odd prime number and $u_i$ strict positive integer. With LTE we get :

$v_{p_i} [(a+1)^n-a^n] = v_{p_i}(1) + v_{p_i}(\frac{n}{p}) = u_i - 1 \leq u_i$ Then $n \nmid (a+1)^n-a^n$
( if we write $(a+1)^n-a^n = ((a+1)^{p_i})^{\frac{n}{p_i}} - ((a^{p_i})^{\frac{n}{p_i}}$ )

Then if n=1, the result is always integer so the only solution is $n=1$ .

blud forgot the 3 conditions for lte to work

Z K Y