Skip to main content

New answers tagged

0 votes

Quadratic irrationals with continued fraction of period one

Let $p/q$ be a rational fraction and $p'/q'$ be its penultimate CF approximant, both rendered in lowest terms. If $m=\frac12(n+\sqrt{n^2+4})$ is a metallic mean, then the CF for the ratio $\dfrac{mp+p'...
Oscar Lanzi's user avatar
0 votes

There exist two square-free numbers, each with a given amount of factors, that differ by a given amount.

This is an incomplete answer, relating your question to Dickson's conjecture which is presently unproven. It does suggest that your claim holds when $m,n>1$, and I'm sure that with some effort or a ...
Servaes's user avatar
  • 65.6k
0 votes
Accepted

Can two irrational numbers satisfy these conditions?

Take $$P= \frac12 \left(1 + 3 \sqrt2 + \sqrt{15 + 6 \sqrt2}\right)$$ And $$Q=\frac12 \left(-1 + 3 \sqrt2 - \sqrt{15 - 6 \sqrt2}\right)$$ The values of your expressions are, in order, $$17$$ $$\frac{19+...
Bruno Andrades's user avatar
1 vote
Accepted

How to prove $ax+by\equiv c\pmod{n}$ has a solution if and only if $gcd(a,b,n)\mid c$?

According to Bézout's identity, there exist three integers $x_1, x_2, x_3$ such that $ a x_1 + b x_2 + n x_3 = d $ We know that $c = d e$ for some integer $e$. Hence $ a e x_1 + b e x_2 + n e x_3 = c $...
math_qa's user avatar
  • 57
0 votes
Accepted

Symmetry (group) arising from modular arithmetic

The question, in essence, asks that, given $k\not \equiv \pm 1\pmod n$, and given $a\pmod n$ can we always find $i, j\pmod n$ such that $$i+kj\equiv 0 \quad \quad \&\quad \quad j+ki\equiv a \tag1$$...
lulu's user avatar
  • 75.3k
3 votes

Number Theory Problem related to GCD and sequence from an Olympiad

Another way. These two preliminary results are easy to prove ► By telescopy we have $a_n+n=a_0+(a_0^2+a_1^2+....+a_{n-1}^2)$ for all $n\ge1$. ►► If $p|a_n$ then $a_{n+k}\equiv-1\pmod p$ for all $k$. ...
Piquito's user avatar
  • 31.3k
2 votes
Accepted

Satisfying $Sd(S)$ modular conditions with $O(S)$ points

Let $S=p^n$ for a prime $p$. For $k=0,\cdots, p^n-1$, let $x_k=k$. Write $k$ as an $n$ digit number base $p$ and reverse the digits (including leading $0$'s up to $n$'th digit) and let $y_k$ be the ...
tkf's user avatar
  • 14k
0 votes

How far away is a number from being a power?

You can trivially calculate the 2nd, 3rd, 4th etc root of n, rounded to the nearest integer. And you don't need k-th roots where k is composite, saving quite a lot of work. For small n, say n ≤ 10^10, ...
gnasher729's user avatar
  • 10.3k
6 votes
Accepted

How far away is a number from being a power?

The distance from $n$ to the nearest $k$th power of an integer is exactly $\min\{ n-\lfloor m^{1/k}\rfloor^k,\lceil m^{1/k}\rceil^k - n \}$. Therefore if $n\le2^B$, the distance from $n$ to the ...
Greg Martin's user avatar
  • 86.9k
1 vote
Accepted

What types of operations on linear congruences yield extraneous solutions?

While performing $7x-(39x-5\cdot7x)$, "equation $(17)$" was multiplied by $1-(-5)$, which is not coprime to $39$. Other point of view: "equation $(17)$" is equivalent to equation $(...
Anne Bauval's user avatar
  • 44.2k
2 votes
Accepted

Show 7 is a generator of $\left(\mathbb{Z} \backslash p \mathbb{Z} \right)^*$ given that it is a quadratic noresidue.

Since $7$ is a quadratic non-residue modulo $p$, it follows that $7^{\frac{p-1}{2}} \equiv -1 \pmod p$. Since $p = 2^{2^n} + 1$, this implies $7^{2^{2^n -1}} \equiv -1 \pmod{p}$, which implies that $7^...
Anuradha N.'s user avatar
3 votes

Does using pre-computed squares speed up significantly the calculation of factorial $n!$?

Let say I need to calculate $1000!$. $1000!$ has $2568$ digits in base$10$, so we have to pre-compute all the squares up to $10^{2568}$ (approx). It is not possible to store the table with this size ...
anton platonov's user avatar
2 votes

Doubt regarding the prime counting function $\pi(n)$

You may use the bounds $\frac{x}{\log x}\lt \pi(x)\lt \frac{3x}{2\log x}$ for $x\geq 17$. It follows $\pi(n^2)-\pi\left(\left\lfloor \frac{n^2}{2}\right\rfloor\right) \gt \frac{n^2}{2\log n} - \frac{...
Sahaj's user avatar
  • 4,463
5 votes

How *exactly* is divisibility defined?

In addition to freakish’s answer, one might note that in a noncommutative ring (such as the Hurwitz integers $H$, the ring of quaternions with either all integer or all half-integer components), there ...
PunySoloist's user avatar
0 votes

$x$ is rational if $x^5$ and $20x+\frac {19}x$ are rational

Say $x^5 = t,$ $a=20$ & $b=19.$ We proceed as follows: \begin{equation} a^2x^2 + \frac{b^2}{x^2} = \left(ax + \frac{b}{x}\right)^2 - 2ab \in \mathbf{Q} \tag{1} \end{equation} \begin{equation} a^...
Akshat Mishra's user avatar
0 votes

If $(a, b) = 1$ and $n$ is a prime then prove that $\frac{a^n+b^n}{a+b}$ and $a+b$ have no common factors unless $a+b$ is a multiple of $n$.

Here's a relatively standard solution using LTE. Suppose $p$ is a prime that divides $a+b$. In particular; if $n\nmid a+b$ then $p\neq n$. Notice that since $a,b$ are coprime, and $p\mid a+b$, then $p\...
Bruno Andrades's user avatar
0 votes

If $(a, b) = 1$ and $n$ is a prime then prove that $\frac{a^n+b^n}{a+b}$ and $a+b$ have no common factors unless $a+b$ is a multiple of $n$.

For any positive integer $n$, $$ a^n + b^n = a^n + (( a+b) + (-a))^n = a^n(1 + (-1)^n) + (a + b)^n + \sum_{j = 1}^{n-1} {n \choose j} (a + b)^j (-a)^{n-j}$$ CASE I: $n$ is an odd prime. The $a^n$ term ...
Shivay Vadhera's user avatar
3 votes
Accepted

at least $n^2$ different integers of the form $x+yz$ where $x,y,z \in S$

Hint You can prove this by induction on $n$. Let $m$ be the largest number in $S$, and let $S'=S-\{m\}$. By the inductive hypothesis, you know that there are at least $(n-1)^2$ numbers of the form $xy+...
Mike Earnest's user avatar
8 votes

How *exactly* is divisibility defined?

Generally in a commutative ring (or monoid) $R,$ by definition $\,a\mid b\,$ if $\,ax=b\,$ has a solution in $R$, unique $ $ iff $\,a\,$ is not a zero divisor, $ $ so then $\:a\mid b\iff b/a\in R\:$ ...
Bill Dubuque's user avatar
60 votes

How *exactly* is divisibility defined?

The most general definition is: We will say that $a$ divides $b$ if there is $c$ such that $b=ac$. Here $a,b,c$ are assumed to belong to the same "structure". I deliberately omitted the &...
freakish's user avatar
  • 46.3k
4 votes
Accepted

Finding Pythagorean triples divisible into smaller Pythagorean Triples.

Here's a way to generate more examples, several of which are "small" by some metric. Given any triple $(a, b, c)$, scaling it by $c$ produces the triple $(ca, cb, c^2)$, so the hypotenuse ...
Sammy Black's user avatar
  • 27.5k
1 vote

Multiplication Well Defined Under Integers

Observation: Verify the following : We can multiply throughout by a scalar, namely $(kA, kB) \sim (k\bar{A} , k\bar{B})$. We can swap coordinates, namely $(B, A) \sim (\bar{B}, \bar{A})$. We can add ...
Calvin Lin's user avatar
  • 74.1k
1 vote

How to determine the PDF of $\{a+bx\}$, the fractional part of a linear function?

$\DeclareMathOperator{\fp}{\mathrm{frac}}\DeclareMathOperator{\P}{\mathbb{P}}$Let $X$ be a random variable uniformly distributed over the set $\{1,2,\ldots,N\}$, that is $$\P(X=k)=\frac1N,$$ for all $...
framago's user avatar
  • 1,113
3 votes
Accepted

Can this pattern connect trigonometry and repeating decimals?

Let $$ a(x)=\frac{10^{9d}-1}{x} $$ where $x$ is a positive integer such that $1/x$ has a non terminating decimal fraction and $d$ is the period of repetition of that decimal fraction. Let the last ...
David K's user avatar
  • 103k
1 vote

Diophantine equation: finding when a degree $2$ expression in $x$ and $y$ is a perfect square.

If you set $2x-y-1=u$ and $y-x=v$, you get a bijection between $\mathbb{Z}^2$ and $\mathbb{Z}^2$, which means that each integer solution for $(x,y)$ is also an integer solution for $(u,v)$ and the ...
Reinhard Meier's user avatar
0 votes

Diophantine equation: finding when a degree $2$ expression in $x$ and $y$ is a perfect square.

$$k^2=4x^2-4x(y-1)+y^2-6y+1\iff4x^2-4x(y-1)+y^2-6y+1-k^2=0$$ $$\implies x=\cdots=\dfrac{y-1\pm\sqrt{k^2+4y}}2$$ Now, as $x$ is an integer, $\sqrt{d^2+4y}$ must be an integer $=+e$(say) $\implies y=\...
lab bhattacharjee's user avatar
0 votes

If none of numbers: $a,a+d,a+2d,...,a+(n-1)d$ are divisible by $n$,then prove that $n,d$ are coprime.

If $\gcd(n, d) = 1$, then we will have,$(i-j)d \equiv 0 \pmod{n}$, implying that $i-j \equiv 0 \pmod{n}$, but this is impossible since both $i$ and $j$ are less than $n$, so $\gcd(n, d) \neq 1$
Ted's user avatar
  • 3
1 vote

Can this pattern connect trigonometry and repeating decimals?

Not an answer, but an attempt to re-state the question. Some observations: For rational $s$ (strictly) between $0$ and $1$, with a repetend of length $d$ that starts immediately after the decimal ...
Blue's user avatar
  • 80.3k
1 vote

How can we know if a multinomial coefficient is even or odd

You can actually work out the complete prime factorization of each factorial in the numerator and denominator pf the multinomial coefficient using Legendre's method In your application you only need ...
MathFont's user avatar
  • 5,535
-1 votes
Accepted

Why do these relations hold for repeating decimals?

Hint e.g. for $\,n=7\,$ the modulus $\,m = 142857 = (\color{#0a0}{10^6-1})/7,\,$ so $\bmod m\,$ we have $\,\color{#0a0}{10^6\equiv 1},\,$ so $\,\color{#c00}{10^{6j}}\equiv (\color{#0a0}{10^6})^j\equiv ...
Bill Dubuque's user avatar
1 vote

Showing there is always rational points on the curve $\sqrt{x^2-1}$, with any given range

Here is a proof based on Gerry Myerson's comments: Let's begin with the easy part: if $x=\frac{q^2+1}{q^2-1}$, where $q$ is a rational number greater than $1$, then both $x$ and $\sqrt{x^2-1}=\frac{2q}...
Gonçalo's user avatar
  • 12.3k
1 vote

Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.

Just to add some details to the nice answers already posted, the subgroup of $(\mathbb{Z}/1000)^{\times}$ generated by $3$ and $7$ has order 200, so it is of index $2$ ( since $|(\mathbb{Z}/1000)^{\...
orangeskid's user avatar
  • 55.6k
1 vote

Non-Trivial Solutions to Diophantine Equation $x^3 + x = y^3$

Note that for $x>0$ you have $$x^3<x^3+x<(x+1)^3,$$ and for $x<0$ you have $$(x-1)^3<x^3+x<x^3.$$ This means $x^3+x$ is not a perfect cube if $x\neq0$, so the unique integral ...
Servaes's user avatar
  • 65.6k
10 votes

Find all $a$ such that $n^{a}-n$ is divisible by $a \cdot (a-1)$ for any integer $n$.

For $a=1$ the problem reduces to $0\mid0$, which is true, so this is another (trivial) solution. Now let $a>1$. By Korselt's criterion, as linked in the comments, $a-1$ has to be squarefree, and ...
anankElpis's user avatar
  • 2,703
2 votes

Composite $2^{398}+1$ in its prime factors.

As explained in the comments, $$ 2^{398}+1=(1-2^{100}+2^{199})(1+2^{100}+2^{199}). $$ This is enough for pari-gp to factorize it: \begin{align*} 1-2^{100}+2^{199}& =797 \\ & \cdot ...
Dietrich Burde's user avatar
2 votes
Accepted

Enumeration of Permutations of $0–9$ Satisfying Closure Under Doubling

You’ve seen that we have these constraints on valid numbers (SMART numbers whose double is SMART): (a) each digit is used exactly once; (b) the first digit is less than $5$; (c) for $0 ≤ i < 5$, ...
Anders Kaseorg's user avatar
0 votes

Is it known that all primes can be expressed as a square number minus a prime number?

Comment: I found this in a book which can help to formulate the matter. Problem: Prove that any number $n>6$ can be expressed as the sum of two numbers prime to each other. Solution: case 1: the ...
sirous's user avatar
  • 11.6k
0 votes

Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.

If we look at the group generated by 3 modulo 100. 3,9,27,81,43,29, etc. There are 20 members to this group. Every element has an even number in the 10s digit. 7 is a member of the group. All numbers ...
user317176's user avatar
-1 votes

Divisibility by $33^{33}$

My approach to this problem was quite simple. I found for which values of $k$ is $19^k+92^k$ divisible by $3$,$11$ or $33$. I found out that: $3 \mid 19^k+92^k$ when $k$ is odd, and $3^2|19^k+92^k$ ...
Brayant Tagne's user avatar
4 votes

Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.

Proof$_{\:\!1}$ $\!\bmod 20\!:\, 7\equiv 3^{-1}$ so $\,3^a7^b\!\equiv 3^{a-b}\!\in S\equiv \{1,3,9,7\}\,$ but $\,133\!\equiv\! 13\not\in S$ $\,\ \bf\small QED$ Proof$_{\:\!2}$ $ \bmod 4\!:\, \ \ \ \...
Bill Dubuque's user avatar
4 votes

Given an $n$ such that for all $m \neq n$, then $\phi(n) \neq \phi(m)$, prove that $4 \mid n$

Answering for completion : If $n$ is not a multiple of $4$, then $n$ is either odd or an odd multiple of $2$. If $n=2k$ with $k$ odd then $\phi(n) = \phi(2k) = \phi(2)\phi(k) = \phi(k)$. If $n$ is odd ...
Sarvesh Ravichandran Iyer's user avatar
17 votes

Is it known that all primes can be expressed as a square number minus a prime number?

This seems to be unknown, and like many problems of this form, hard to approach. Indeed, in this case even if it was not true for some particular prime $p^*$, how would you even prove that $n^2-p^*$ ...
Especially Lime's user avatar
13 votes
Accepted

Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.

The remaining other possibility is that the number, call it $n$, has the form $3^a7^b$. If we know the three last digits of a natural number, we also know its residue class modulo $8$. As $133\equiv5\...
Jyrki Lahtonen's user avatar
6 votes

Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.

Not much case analysis is actually necessary here. Say $n$ ends in $133$. It certainly isn't divisible by $2$ or $5$; so we need to show it can't be of the form $3^a 7^b$. You can do this by looking ...
Chris Lewis's user avatar
  • 3,278
4 votes

Show that no positive integer ending in $133$ can be expressed in the form $3^a7^b$, where $a$ and $b$ are non-negative integers.

A number with no prime factors greater than $7$ must have only prime factors in $\{2,3,5,7\}$. Such a number takes the form $2^a3^b5^c7^d$. If $n\equiv 133\bmod 1000$ takes this form, it must have no $...
Joshua Tilley's user avatar
0 votes
Accepted

Digit Factorial Chains - Why does every number fall into a loop?

Some notation : for $N \in \mathbb N$ let $f(N)$ be the sum of the factorials of the digits of $N$. Let $N$ be an $n$ digit number with $n$ fixed. Then, $f(N)$ is the largest when each of its digits ...
Sarvesh Ravichandran Iyer's user avatar
1 vote

Criteria for a number being a square-pyramidal number

We can identify a square pyramidal number by comparing it with with an appropriately constructed cube. Multiply the number to be tested by $24$, e.g. $91×24=2184.$ Identify the cube root of this ...
Oscar Lanzi's user avatar
7 votes
Accepted

Criteria for a number being a square-pyramidal number

Let's work this out in general. Suppose we wish to test whether $K = P(n)$, where $P(x)$ is a polynomial in $\mathbb{Q}[x]$. Assume there exists a polynomial $Q(x) \in \mathbb{Q}[x]$ and an integer $m ...
Benjamin Wright's user avatar
0 votes

$a^2 = 3^b + 37$

Comment: Starting from the solutions you found we may try to pridict the existence of more solutions. We may manipulate like this: $3^b+3^3=a^2-10\Rightarrow a^2-10\geq 27$ In the case $a^2=27$ we ...
sirous's user avatar
  • 11.6k
-1 votes

$a^2 = 3^b + 37$

if you would change it for 2log(a)=b*log(3)+37 ...
A. P. Kodzis's user avatar

Top 50 recent answers are included