Tallteorimaraton
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
(Noah sin løsning)
For skal bruke følgende formler for $\sigma(n)$ og $\phi(n)$:
\begin{align*}
\phi(n) &= (p_1^{i_1}-p_1^{i_1-1})\dots(p_k^{i_k}-p_k^{i_k-1}) \\
\sigma(n) &= (p_1^{i_1}+p_1^{i_1-1}+\dots +1)\dots(p_k^{i_k}+p_k^{i_k-1}+\dots + 1)
\end{align*}
der $n = p_1^{i_1}\dots p_k^{i_k}$.
Vi deler det inn i 3 cases, at n har 1 primdivisor, 2 primdivisorer og flere enn 2 primdivisorer.
$\underline{\textbf{1 primdivisor}}$
La $p$ være denne primdivisoren. Vi får at
\begin{align*}
\phi(n) + \sigma(n) &= (p^k-p^{k-1}) + (p^k + p^{k-1} + \dots + 1) \\
&= 2p^k + p^{k-2} + \dots + 1 \\
&= 2n + p^{k-2} + \dots + 1
\end{align*}
Eneste måten $p^{k-2} + \dots + 1$ kan bli 8 er dersom $p=7$ og $k=3$, så vi har funnet løsningen $n=343$.
$\underline{\textbf{Flere enn 2 primdivisorer}}$
Vi skriver $n = p_1^{i_1}\dots p_k^{i_k}$. Da får vi at
\begin{align*}
\phi(n) + \sigma(n) &\geq (p_1^{i_1}-p_1^{i_1-1})\dots(p_k^{i_k}-p_k^{i_k-1}) + (p_1^{i_1}+p_1^{i_1-1})\dots(p_k^{i_k}+p_k^{i_k-1}) \\
&\geq 2p_1^{i_1}\dots p_k^{i_k} + 2\sum_{i=1}^k p_i^{j_k} \\
&\geq 2n+10
\end{align*}
Summen er slik at $j_k=i_k$ for alle utenom 2 av indeksene, der vi har $j_k = i_k-1$. Da er den summen minst lik summen av 3 forskjellige primtall, som åpenbart er $\geq 10$.
$\underline{\textbf{2 primvidisorer}}$
La $n = p^kq^m$. Vi får at
\begin{align*}
\phi(n) + \sigma(n) &\geq (p^k+p^{k-1})(q^m+q^{m-1}) + (p^k-p^{k-1})(q^m-q^{m-1}) \\
&= 2p^kq^m + 2p^{k-1}q^{m-1} \\
&= 2n + 2p^{k-1}q^{m-1}
\end{align*}
Vi ser at dersom $k,m\geq 2$ har vi ingen løsninger. For $k=m=1$ har vi $\phi(n)+\sigma(n) = (p-1)(q-1) + (p+1)(q+1) = 2pq+2 = 2n$, som ikke gir en løsning. Dersom vi WLOG antar $p \leq q$ har vi at $m = 1$, og får at
\begin{align*}
\phi(n) + \sigma(n) &\geq (p^k-p^{k-1})(q-1)+(p^k + p^{k-1}+1)(q+1) \\
&= 2p^kq + 2p^k + q + 1 \\
&= 2n + 2p^k + q + 1
\end{align*}
Dette er stemmer bare dersom $p=k=2$ og $q=3$, som gir $n=12$.
Alle løsningene er dermed $\fbox{$n=12$ og $n=343$}$
For skal bruke følgende formler for $\sigma(n)$ og $\phi(n)$:
\begin{align*}
\phi(n) &= (p_1^{i_1}-p_1^{i_1-1})\dots(p_k^{i_k}-p_k^{i_k-1}) \\
\sigma(n) &= (p_1^{i_1}+p_1^{i_1-1}+\dots +1)\dots(p_k^{i_k}+p_k^{i_k-1}+\dots + 1)
\end{align*}
der $n = p_1^{i_1}\dots p_k^{i_k}$.
Vi deler det inn i 3 cases, at n har 1 primdivisor, 2 primdivisorer og flere enn 2 primdivisorer.
$\underline{\textbf{1 primdivisor}}$
La $p$ være denne primdivisoren. Vi får at
\begin{align*}
\phi(n) + \sigma(n) &= (p^k-p^{k-1}) + (p^k + p^{k-1} + \dots + 1) \\
&= 2p^k + p^{k-2} + \dots + 1 \\
&= 2n + p^{k-2} + \dots + 1
\end{align*}
Eneste måten $p^{k-2} + \dots + 1$ kan bli 8 er dersom $p=7$ og $k=3$, så vi har funnet løsningen $n=343$.
$\underline{\textbf{Flere enn 2 primdivisorer}}$
Vi skriver $n = p_1^{i_1}\dots p_k^{i_k}$. Da får vi at
\begin{align*}
\phi(n) + \sigma(n) &\geq (p_1^{i_1}-p_1^{i_1-1})\dots(p_k^{i_k}-p_k^{i_k-1}) + (p_1^{i_1}+p_1^{i_1-1})\dots(p_k^{i_k}+p_k^{i_k-1}) \\
&\geq 2p_1^{i_1}\dots p_k^{i_k} + 2\sum_{i=1}^k p_i^{j_k} \\
&\geq 2n+10
\end{align*}
Summen er slik at $j_k=i_k$ for alle utenom 2 av indeksene, der vi har $j_k = i_k-1$. Da er den summen minst lik summen av 3 forskjellige primtall, som åpenbart er $\geq 10$.
$\underline{\textbf{2 primvidisorer}}$
La $n = p^kq^m$. Vi får at
\begin{align*}
\phi(n) + \sigma(n) &\geq (p^k+p^{k-1})(q^m+q^{m-1}) + (p^k-p^{k-1})(q^m-q^{m-1}) \\
&= 2p^kq^m + 2p^{k-1}q^{m-1} \\
&= 2n + 2p^{k-1}q^{m-1}
\end{align*}
Vi ser at dersom $k,m\geq 2$ har vi ingen løsninger. For $k=m=1$ har vi $\phi(n)+\sigma(n) = (p-1)(q-1) + (p+1)(q+1) = 2pq+2 = 2n$, som ikke gir en løsning. Dersom vi WLOG antar $p \leq q$ har vi at $m = 1$, og får at
\begin{align*}
\phi(n) + \sigma(n) &\geq (p^k-p^{k-1})(q-1)+(p^k + p^{k-1}+1)(q+1) \\
&= 2p^kq + 2p^k + q + 1 \\
&= 2n + 2p^k + q + 1
\end{align*}
Dette er stemmer bare dersom $p=k=2$ og $q=3$, som gir $n=12$.
Alle løsningene er dermed $\fbox{$n=12$ og $n=343$}$
-
Lil_Flip39
- Cayley
- Innlegg: 69
- Registrert: 25/04-2024 12:57
- Sted: Oslo
Svaret er $\fbox{(m,n)=(9,3),(6,3),(9,5),(54,5)}$.
det er åpenbart at $m\mid 2\times 3^n$
anta først $m=2\times 3^k$
plugg inn og forenkling gir:
$2\times 3^k+3^{n-k}=2^{n+1}-1$
Vi ser at $n$ må være odde for at $3$ skal dele høyre side.
Derfor har vi av LTE at $v_p(2^{n+1}-1)=v_p(\frac{n+1}{2})+1$.
Nå gjør vi casework(likhet kan ikke holde under siden odde):
1) $k<n-k$
Vi får da $v_p(\frac{n+1}{2})+1=n-k$, eller
$\frac{n+1}{2}\geqslant 3^{n-k-1}$ for $k<\frac{n}{2}$
som åpenbart bare holder for små $n$
2) $n-k<k$
Vi får da $v_p(\frac{n+1}{2})+1=k$, eller
$\frac{n+1}{2}\geqslant 3^{k-1}$ for $k>\frac{n}{2}$
som også bare holder for små $n$.
En lett skjekk gir $n=3,5$, som gir løsningene $\fbox{(6,3),(54,5)}$.
når $m=3^k$ er løsningen lik, da får man løsningene $\fbox{(9,3),(9,5)}$
det er åpenbart at $m\mid 2\times 3^n$
anta først $m=2\times 3^k$
plugg inn og forenkling gir:
$2\times 3^k+3^{n-k}=2^{n+1}-1$
Vi ser at $n$ må være odde for at $3$ skal dele høyre side.
Derfor har vi av LTE at $v_p(2^{n+1}-1)=v_p(\frac{n+1}{2})+1$.
Nå gjør vi casework(likhet kan ikke holde under siden odde):
1) $k<n-k$
Vi får da $v_p(\frac{n+1}{2})+1=n-k$, eller
$\frac{n+1}{2}\geqslant 3^{n-k-1}$ for $k<\frac{n}{2}$
som åpenbart bare holder for små $n$
2) $n-k<k$
Vi får da $v_p(\frac{n+1}{2})+1=k$, eller
$\frac{n+1}{2}\geqslant 3^{k-1}$ for $k>\frac{n}{2}$
som også bare holder for små $n$.
En lett skjekk gir $n=3,5$, som gir løsningene $\fbox{(6,3),(54,5)}$.
når $m=3^k$ er løsningen lik, da får man løsningene $\fbox{(9,3),(9,5)}$
-
Lil_Flip39
- Cayley
- Innlegg: 69
- Registrert: 25/04-2024 12:57
- Sted: Oslo
ny oppgave:
FInn alle heltall $s>3$ slik at det finnes positive heltall $a,b,c,d$ som oppfyller følgene kriterier:
i) $s=a+b+c+d$
II) $s$ deler $abc+abd+acd+bcd$
FInn alle heltall $s>3$ slik at det finnes positive heltall $a,b,c,d$ som oppfyller følgene kriterier:
i) $s=a+b+c+d$
II) $s$ deler $abc+abd+acd+bcd$
Sist redigert av Lil_Flip39 den 20/11-2024 22:08, redigert 1 gang totalt.
For å gi svar på den redigerte oppgaven til Lil_Flip39:
$\fbox{Det går for alle sammensatte heltall}$
$\underline{\text{Claim 1: Sammensatt $s$ gir løsning}}$
Vi skriver $s = x \cdot y = ((x-1)+1)((y-1)+1) = (x-1)(y-1) + (x-1) + (y-1) + 1$, og velger $a,b,c,d$ til å være disse 4 leddene.
Videre kan vi regne ut at $abc+abd+acd+bcd = xy(x-1)(y-1)$, som det er åpenbart at $s$ deler.
$\underline{\text{Claim 2: Primtall $s$ gir ikke løsning}}$
Vi skriver $a+b+c+d=p$, og det gir at $a+b \equiv -(c+d)\mod{p}$. Videre skriver vi om delelighetskravet til $p$:
\begin{align*}
p &| abc+abd+acd+bcd \\
p &| ab(c+d) + cd(a+b)\\
p &| (c+d)(ab-cd) \\
p &| (c+d)(ab-cd) + c(c+d)(a+b+c+d) \\
p &| (c+d)(ab-cd+ac+bc+c^2+cd) \\
p &| (c+d)(a+c)(b+c) \\
\end{align*}
Siden $p$ er et primtall har vi at
\[
p|c+d \hspace{5mm} \text{eller} \hspace{5mm} p|a+c \hspace{5mm} \text{eller} \hspace{5mm} p|b+c
\]
som er en motsigelse, siden $0<u+v<p$ når $u,v\in\{a,b,c,d\}$ med $u\neq v$. Dermed fungerer ikke primtall, og vi er ferdig.
$\fbox{Det går for alle sammensatte heltall}$
$\underline{\text{Claim 1: Sammensatt $s$ gir løsning}}$
Vi skriver $s = x \cdot y = ((x-1)+1)((y-1)+1) = (x-1)(y-1) + (x-1) + (y-1) + 1$, og velger $a,b,c,d$ til å være disse 4 leddene.
Videre kan vi regne ut at $abc+abd+acd+bcd = xy(x-1)(y-1)$, som det er åpenbart at $s$ deler.
$\underline{\text{Claim 2: Primtall $s$ gir ikke løsning}}$
Vi skriver $a+b+c+d=p$, og det gir at $a+b \equiv -(c+d)\mod{p}$. Videre skriver vi om delelighetskravet til $p$:
\begin{align*}
p &| abc+abd+acd+bcd \\
p &| ab(c+d) + cd(a+b)\\
p &| (c+d)(ab-cd) \\
p &| (c+d)(ab-cd) + c(c+d)(a+b+c+d) \\
p &| (c+d)(ab-cd+ac+bc+c^2+cd) \\
p &| (c+d)(a+c)(b+c) \\
\end{align*}
Siden $p$ er et primtall har vi at
\[
p|c+d \hspace{5mm} \text{eller} \hspace{5mm} p|a+c \hspace{5mm} \text{eller} \hspace{5mm} p|b+c
\]
som er en motsigelse, siden $0<u+v<p$ når $u,v\in\{a,b,c,d\}$ med $u\neq v$. Dermed fungerer ikke primtall, og vi er ferdig.
Vel nå har det seg slik at noen andre postet oppgaven kanskje, og jeg hadde ikke løst den selv så:
Vi viser at det ikke finnes noen løsning
Vi faktoriserer først utrykket for å få noe mer nice.
WLOG anta
Observer at ligningen er ekvivalent med at:
[tex]p^3+1=pq^3+q^3[/tex]
[tex](p+1)(p^2-p+1) = (p+1)q^3[/tex]
[tex]p^2-p+1=q^3[/tex]
Her ser vi også at [tex]p>q[/tex]
[tex]p(p-1)=(q-1)(q^2+q+1)[/tex]
Av dette får vi at [tex]q-1 | p-1[/tex]
Dermed vil det finnes k slik at:
[tex]p = kq-k+1[/tex]
Vi får også at
[tex]p | q^2+q+1[/tex]
[tex] kq-k+1| k(q^2+q+1) [/tex]
[tex]kq-k+1| k(q^2+q+1)-q(kq-k+1) [/tex]
Og videre:
[tex]kq-k+1 | k-q[/tex]
Anta q > k
Da får vi
[tex]kq-k+1 < q-k[/tex]
[tex](k-1)(q-1) < -k[/tex]
Som åpenbart er feil, siden k er negativ.
Hvis k > q får vi da:
[tex]kq-k+1 < k-q[/tex]
[tex](k-1)(q-1) < k-2q < k[/tex]
Som gir at q =2 er det eneste som er mulig
Men ved å plugge det inn i ligningen får vi at:
[tex]p^2-p+1=8[/tex]
Som åpenbart ikke har noen løsninger
Vi viser at det ikke finnes noen løsning
Vi faktoriserer først utrykket for å få noe mer nice.
WLOG anta
Observer at ligningen er ekvivalent med at:
[tex]p^3+1=pq^3+q^3[/tex]
[tex](p+1)(p^2-p+1) = (p+1)q^3[/tex]
[tex]p^2-p+1=q^3[/tex]
Her ser vi også at [tex]p>q[/tex]
[tex]p(p-1)=(q-1)(q^2+q+1)[/tex]
Av dette får vi at [tex]q-1 | p-1[/tex]
Dermed vil det finnes k slik at:
[tex]p = kq-k+1[/tex]
Vi får også at
[tex]p | q^2+q+1[/tex]
[tex] kq-k+1| k(q^2+q+1) [/tex]
[tex]kq-k+1| k(q^2+q+1)-q(kq-k+1) [/tex]
Og videre:
[tex]kq-k+1 | k-q[/tex]
Anta q > k
Da får vi
[tex]kq-k+1 < q-k[/tex]
[tex](k-1)(q-1) < -k[/tex]
Som åpenbart er feil, siden k er negativ.
Hvis k > q får vi da:
[tex]kq-k+1 < k-q[/tex]
[tex](k-1)(q-1) < k-2q < k[/tex]
Som gir at q =2 er det eneste som er mulig
Men ved å plugge det inn i ligningen får vi at:
[tex]p^2-p+1=8[/tex]
Som åpenbart ikke har noen løsninger
-
Solar Plexsus
- Over-Guru
- Innlegg: 1686
- Registrert: 03/10-2005 12:09
La $n$ være antalll siffer i $a$. Da er
$(1) \;\; 10^{n-1} \leq a < 10^n$.
Likningen
${\textstyle (2) \;\; \frac{a}{b} = \overline{b.a}}$
er ekvivalent med
${\textstyle \frac{a}{b} = b + \frac{a}{10^n}}$,
i.e.
$(3) \;\; (a - b^2) \cdot 10^n = ab$.
Anta at $p$ er en primtallsdivisor av $a - b^2$ og $ab$. Da må $p \mid ab$ og $p \mid a - b^2$, som enten impliserer at $p \mid a$ og $p \mid b^2$ eller $p \mid b$ og $p \mid a$. Følgelig må $p \mid GCD(a,b)=1$. Denne selvmotsigelsen gir $GCD(a-b^2,ab)=1$, et faktum som i kombinasjon med likning (3) resulterer i
$(4) \;\; a - b^2 =1$,
som innsatt i likning (3) gir
$(5) \;\; ab = 10^n$.
Ifølge likningene (4) og (5) er $a>b>1$, som kombinert med $GCD(a,b)=1$ og likning (5) medfører at
$(6) \;\; (a,b)=(5^n,2^n)$,
som ifølge likning (4) gir
$(6) \;\; 5^n - 4^n = 1$,
som har $n=1$ som eneste løsning ettersom $5^n - 4^n$ vokser når $n$ vokser. Formlene (6) gir oss følgende konklusjon:
Det eneste paret av positive innbyrdes primiske heltall som tilfredsstiller likning (2) er $(a,b)=(5,2)$.
$(1) \;\; 10^{n-1} \leq a < 10^n$.
Likningen
${\textstyle (2) \;\; \frac{a}{b} = \overline{b.a}}$
er ekvivalent med
${\textstyle \frac{a}{b} = b + \frac{a}{10^n}}$,
i.e.
$(3) \;\; (a - b^2) \cdot 10^n = ab$.
Anta at $p$ er en primtallsdivisor av $a - b^2$ og $ab$. Da må $p \mid ab$ og $p \mid a - b^2$, som enten impliserer at $p \mid a$ og $p \mid b^2$ eller $p \mid b$ og $p \mid a$. Følgelig må $p \mid GCD(a,b)=1$. Denne selvmotsigelsen gir $GCD(a-b^2,ab)=1$, et faktum som i kombinasjon med likning (3) resulterer i
$(4) \;\; a - b^2 =1$,
som innsatt i likning (3) gir
$(5) \;\; ab = 10^n$.
Ifølge likningene (4) og (5) er $a>b>1$, som kombinert med $GCD(a,b)=1$ og likning (5) medfører at
$(6) \;\; (a,b)=(5^n,2^n)$,
som ifølge likning (4) gir
$(6) \;\; 5^n - 4^n = 1$,
som har $n=1$ som eneste løsning ettersom $5^n - 4^n$ vokser når $n$ vokser. Formlene (6) gir oss følgende konklusjon:
Det eneste paret av positive innbyrdes primiske heltall som tilfredsstiller likning (2) er $(a,b)=(5,2)$.
-
Lil_Flip39
- Cayley
- Innlegg: 69
- Registrert: 25/04-2024 12:57
- Sted: Oslo
Siden ingen har lagt ut ny oppgave, har jeg en her:
Find all prime numbers $p$ and $q$ such that
$$1 + \frac{p^q - q^p}{p + q}$$
is a prime number.
Find all prime numbers $p$ and $q$ such that
$$1 + \frac{p^q - q^p}{p + q}$$
is a prime number.