Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [elementary-number-theory]

Questions on congruences, linear Diophantine equations, greatest common divisor, divisibility, etc.

1
vote
0answers
40 views

Why do perfect square values to $ax^2 +ax +1$ form an exponential function?

While playing around with numbers using Python, I found that the set of values of x which fulfilled $$ax^2 + ax +1 = p^2$$ Where p is an integer form an exponential function. For example, $$3x^2 + ...
0
votes
0answers
12 views

Interpolation Polynomials with Integer coefficients

Suppose we have an ordered list of real values: $$x_1,x_2,x_3,...,x_N \in \mathbb R$$ Now if we consider the set in $\mathbb R^{2}$ (ie with their ordering index as the first variable) : $${\{(1,...
4
votes
3answers
54 views

Taking square roots modulo $2^N$

I was trying to solve $y^2 - y \equiv 16 \pmod{512}$ by completing the square. Here is my solution. \begin{align} y^2 - y &\equiv 16 \pmod{512} \\ 4y^2 - 4y + 1 &\equiv 65 \pmod{512} \\ ...
1
vote
0answers
50 views

Can I switch the order of taking minimums?

Suppose I have some function $F(x,y):\mathbb{R}^2 \rightarrow \mathbb{R}$. Is it always the case that $$ \min_{1 \leq x \leq N} (\min_{1 \leq y \leq M} |F(x,y)|) = \min_{1 \leq y \leq M} (\min_{1 \...
2
votes
0answers
22 views

Conjecture about congruences arising from a special semiprime

Let $k$ be a positive integer such that $p=2k+1$ and $q=4k+1$ are both prime. Consider the number $$N=pq$$ I proved that for every positive integer $a$ coprime to $N$ we have $$a^{N-1}\equiv 1\mod N$$ ...
0
votes
0answers
24 views

Does the relationship $c^ n ±1= 2^{kn−2}d^n$ have solutions in the integers?

In a previous question Can a square number plus 1 become a square? the questioner asked in passing at the end whether $a^n+1$ could ever be a perfect square (for $a \ge 1$ and $n \ge 2$). I provided a ...
0
votes
0answers
28 views

given a Diophantine equation $ax+by=k$ for which $k$ values ​have a solution

given a Diophantine equation $ax+by=k$ and $a,b$ are natural numbers and there $gcd(a,b)=3$ . for which $k$ values ​​have a solution? i try do some examples like $3x+3y=2$ and we see that there is ...
3
votes
4answers
638 views

What is the best algorithm for finding the last digit of an enormous exponent? [duplicate]

I found most answers here not clear enough for my case such as $$ 123155131514315^{4515131323164343214547} $$ I wrote the $n\bmod10$ in Python and execution time ran out. So I need a faster ...
3
votes
0answers
87 views

What is the sum of the even (resp. odd) terms only of the Hockey-stick identity?

The Hockey-stick identity is $$\sum^n_{i=r}{i\choose r}={n+1\choose r+1} \qquad \text{ for } n,r\in\mathbb{N}, \quad n>r$$ I am trying to determine the values of the following $$\sum_{\...
4
votes
1answer
58 views

When is $x^2+y^2+1=xyz$? [duplicate]

Essentially, when is $\dfrac{x^2 +y^2+1}{xy}$ a positive integer? I've tried many approaches such as considering the above equation as a quadratic in $x$ or $y$ but I haven't had much success. The ...
2
votes
1answer
26 views

Prove that there are infinitely many even nontotients

How do I show that there are infinitely many even numbers which are nontotients ? I have proved that $\phi(n)$ is even $\forall\space n>2$ by showing that for the set $Z_n^*$ of all natural ...
3
votes
0answers
37 views

Asymptotic relation between $\Phi(x,z)$ and $\Psi(x,z)$

Define, $\Phi(x,z):=\#\{n\le x: n \text{ is not divisible by any prime }<z\}$ $\Psi(x,z):=\#\{n\le x:\text{ if }p|n \text{ then }p<z\}$. Prove that, $\displaystyle \Phi(x,z)=x\sum_{d|P_z,d\...
1
vote
1answer
69 views

Modular solution to $ax - by \equiv 0\pmod{p}$?

Given prime $p$, integers $x$ and $y$ where both $x, y < p$ and $x \neq y$, is there an efficient way to find nontrivial coefficients $a, b$ where $a, b < \sqrt p$ such that $$ax - by \equiv 0\...
2
votes
1answer
65 views

11 divisiblity problem

Given some digits $d_1, \dots, d_k$ is there a calculation that I can perform to determine if at least 1 permutation of $d_1, \dots, d_k$ is divisible by 11? I am interested in all bases (radices) ...
-1
votes
0answers
24 views

Property of Carmichael Number [on hold]

Prove that for any Carmichael number $x$, $x$ is not divisible by the square of any number and $\forall p \space\space p | x \implies p-1|x-1$ Edit: I've used the following definition: A number $x$ ...
0
votes
1answer
42 views

Elementary Number theory [duplicate]

The sum of several consecutive positive integers is equal to 1000 . Find all such numbers. I don't know where to start , and how to start in solving this question. So please help.
0
votes
0answers
54 views

Concise way to accurately find factors of any number?

The last number of 365 is 5, therefore I’ve been told that 5 is a factor of 365, which it clearly is. This however does not work 100% of the time, I.e. 9 is not a factor of 8599. Also, I’ve been told ...
0
votes
0answers
32 views

Gaussian Primes List

Does anyone have a larger list of the first unique gaussian primes ordered by their norm? Uniqueness can be achieved if one starts with $p_1=1+i$ and requires that for odd primes $p_i \equiv 1 \mod 2+...
3
votes
2answers
73 views

Prove that every natural number $n>15$ there exist natural numbers $x,y\geqslant1$ which solve the equation.

Prove that every natural number $n>15$ exist Natural numbers $x,y\geqslant1$ which solve the equation $3x+5y=n$. so i try induction. base case is for $n=16$. so $\gcd(5,3)=1$, after Euclidean ...
3
votes
2answers
96 views

Number theory - Find the number satisfying the condition.

Find a 3 digit number which equals to 4 times the product of its digits. My approach: I considered the Number to be $\overline{ABC}$ then wrote the relation $$100A+10B+C=4A\times B\times C$$ But i ...
13
votes
5answers
598 views

Integer solutions to $x^3=y^3+2y+1$?

Find all integral pairs $(x,y)$ satisfying $$ x^3=y^3+2y+1.$$ My approach: I tried to factorize $x^3-y^3$ as $$(x-y)(x^2 + xy + y^2)=2y+1,$$ but I know this is completely helpless. Please help me in ...
2
votes
2answers
40 views

Algebra - Solving for three unknowns.

Find all possible solutions of $$2^x + 3^y = z^2.$$ My approach. First I substituted $x = 0$, and got the solution, then for $y = 0$. And for $x > 0$ and $y > 0$ , I just know the ...
0
votes
0answers
21 views

What is the Dirichlet density of all primes whose least residue mod 24 is strictly less than 8

What is the Dirichlet density of all primes whose least residue modulo $24$ is strictly less than $8$? I don't understand the meaning of least residue I know the Dirichlet density of a set of primes ...
2
votes
2answers
50 views

The following equation has several solutions $2x+3y=73$

Given $2x+3y=73$ so we know that the GCD of these is 1 so i do the Euclidean algorithm , i got that $2(3t-73)+3(73+2t)=73$. now if x,y is Rational how many solutions? if x,y is Integers how ...
1
vote
2answers
30 views

Positive Integers to make a square

How many integers $n$ make the expression $7^n + 7^3 + 2\cdot7^2$ a perfect square? Factoring $7^2$ we have that $7^n + 7^3 + 2\cdot7^2 = 7^2\cdot(7^{n-2} + 9)$. How do we prove that the 2nd factor ...
0
votes
1answer
61 views

Least $x$ such that $x \mid (n^x-n)$

Let $x$ be a natural number of the form $3qp$ where $q,p$ are prime. Find the least value of $x$ such that $x \mid (n^x - n)$ for all $n$ in $\Bbb{Z}^+$. I noticed that if $n^x - n$ can be written ...
0
votes
1answer
26 views

How to get the error in the approximation of the number?

I have this exercise: When performing the best approximation by excess to the hundredth of the number $-5,2672$ the error that is committed is The error must be the absolute value of the ...
10
votes
1answer
125 views

Are all numbers of the type $\frac{n!}{2}+1$ deficient?

Are all numbers of the type $\frac{n!}{2}+1$ deficient? Deficient numbers are such numbers $k$, that the divisor sum of $k$ is less than $2k$. I checked all numbers of this type, with $n$ ranging ...
2
votes
1answer
54 views

Proof: If no prime less than or equal to $\sqrt{n}$ divides $n$, then $n$ is a prime [duplicate]

I have the following theorem: If no prime less than or equal to $\sqrt{n}$ divides $n$, then $n$ is a prime. And the following proof (proof by contradiction) for said theorem: Suppose that no ...
0
votes
0answers
17 views

(Soft Question) Largest known Fermat Pseudoprime to a particular base

I am aware that Carmichael Numbers can produce 300-billion-digit long absolute Fermat Pseudoprimes, which are Fermat Pseudoprimes to all coprime bases k. I was wondering if there are larger known ...
4
votes
5answers
68 views

Find all pairs of intergers satisfying $x^2+11 = y^4 -xy$ and $y^2 + xy= 30 $

Find all pairs of intergers $(x,y)$ that satisfy the two following equations: $x^2+11 = y^4 -xy$ $y^2 + xy= 30 $ Here's what I did: $x^2+11 +(30) = y^4 -xy +(y^2 + xy)$ $x^2+41 = y^4 +y^...
1
vote
0answers
33 views

Can a finite set of bases guarantee that a number is Carmichael or prime?

If a positive integer $N>1$ is a Carmichael number, it passes the weak Fermat-pseudoprime-test for every base coprime to it. I wonder whether the converse is true in the following sense : Is ...
1
vote
1answer
68 views

Does there exist a polynomial it does not have any integer root but has at least one root in $\Bbb Z_n$ , $\forall n \in \Bbb Z$?

Does there exist a polynomial $f \in \Bbb Z[X]$ such that $f$ does not have any integer root but $f$ has at least one root in $\Bbb Z_n$ , $\forall n \in \Bbb Z$ ( while considering $f$ as a ...
2
votes
0answers
34 views

What are the properties of abundancy numbers?

Define abundancy numbers as the rational numbers that are equal to the abundancy index of some integer (not to be confused with «abundant numbers», which are natural numbers with abundancyindex ...
0
votes
0answers
21 views

How far was base $47$ checked for a generalized Wieferich-prime?

This question is closely related to : Wieferich primes in base $47$ but I would like to know the current search limit for this base. Upto which prime $p$ was $$47^{p-1}\equiv 1\mod p^2$$ verified ...
1
vote
2answers
51 views

Relation between $\gcd(a, b)$ and $\gcd(a+b, \operatorname{lcm}(a, b))$

I've been trying to figure out a relation between $\gcd(a, b)$ and $\gcd(a+b, \operatorname{lcm}(a, b)).$ I know $$ \gcd(a, b) | (a+b). $$ And, since $a | \operatorname{lcm}(a, b)$ I have $$ \gcd(a, ...
0
votes
4answers
58 views

Natural number that has a remainder of $1, 2, 3, 4$ respectively after dividing… [duplicate]

A number when divided by 2 leaves a remainder of 1. When it is divided by 3 leaves a remainder 2. When it is divided by 4 it leaves a remainder of 3. And when it is divided by 5 it leaves remainder of ...
2
votes
2answers
72 views

Are there any 2 primitive pythagorean triples who share a common leg?

So is it possible for: $\gcd(a,b,c)=1$ $a^2+b^2=c^2$ and $\gcd(a,d,e)=1$ $a^2+d^2=e^2$ ?
3
votes
1answer
30 views

Characterizing the set of positive integers which cannot be represented as $p+a^2$

An exercise in Burton's book "Elementary Number Theory" 7ed, p43 prob 2, is to give a counterexample to the statement: Every positive integer $n$ has a representation $n=p+a^2$, where $p$ is $1$ ...
1
vote
1answer
65 views

integer divides a number, significance [on hold]

I get a factor of $5551$, this is the number I want to investigate. Wolfrom alpha, online mathematics page, shows that this number also divdes $74^3-1$. See, bottom of the page: http://www....
2
votes
1answer
78 views

Find all $m \geq 0$ such that there are no positive integers $x,y$ that satisfy $32xy+10y-3x-1 = 2^m$

Is there any efficient approach to answer this question and similar ones? for $m=0,1,2,3,4,5$ it's easy to see there are no solutions, because the left hand side is at least $32\cdot 1 \cdot 1 + 10 \...
9
votes
2answers
105 views

Quintic reciprocity conjecture

Let $p=x^4 + 25x^2 + 125$ be a prime. Prove that $2$ is a quintic residue $\pmod p$, and therefore $y^5=2\pmod p$ is solvable. A similar example was first conjectured by Euler: If $p=x^2 + 27$ is a ...
4
votes
2answers
120 views

Number theory, possibly mathematical induction to use

For $n, r \in \mathbb{N}$ denote $S_r(n)$ sum $1^r + 2^r + ... + n^r$. Verify that for all $n, r$ : $$(n+1)^{r+1} -(n+1) = \binom{r+1}{1}S_r(n) + \binom{r+1}{2}S_{r-1}(n)+ \cdots +\binom{r+1}{r}S_1(n) ...
6
votes
4answers
350 views

What is the simplest way to rigorously define division (why does the standard algorithm work)?

I become really nervous if I catch myself doing one process without really understanding how it works. Well, one of these processes is division. In primary school, I learned the technique of dividing (...
0
votes
1answer
33 views

Can this quantity be integral?

Let $n,r,k \in \mathbb{N}$. Let $s = \frac{2(r-2)}{\frac{r-k}{n-1}+1}$. The following conditions are given: $3 \leq r \leq n$ $k < r$ My question is: Does there exist any feasible combination ...
2
votes
2answers
67 views

Primes of the form $\ \varphi(n)^{\varphi(n)}+n\ $ or $\ n^n+\varphi(n)\ $ for composite $n$?

This question : Do further prime numbers of the form $n^n+\varphi(n)$ exist? deals about prime numbers of the form $$n^n+\varphi(n)$$ I know no composite number $n$, such that this expression is ...
2
votes
1answer
57 views

Whats the lowest multiple of $99$ that has digits of only $0, 1$, and $ 2$

I was doing a programming problem which is For a positive integer $n$, define $f(n)$ as the least positive multiple of n that, written in base 10, uses only digits $≤ 2$. Thus $f(2)=2, f(3)=12,...
2
votes
4answers
58 views

Does there exist a perfect square of the form $5+40n$?

Does there exist a perfect square of the form $5+40n$ for positive integers $n$? I know this is probably easy to show but any help is appreciated
-5
votes
2answers
66 views

Problem in proof of 0.999…=1? [closed]

There are $n$ nines in the fractional part of $0.\overline9$ But there are $n-1$ nines in the fractional part of $9.\overline9$. Does this affect the proof that $0.\overline9=1$? x=0.99... 10x=9.99... ...
1
vote
1answer
42 views

Parity of the digits present in the sum of a number and its reverse.

Let $S_N$ denote sum of a $N$-digit number and its reverse,then prove; If $N$ is of the form $4k+1$, at least one of the digits of $S_N$ is an even number. If $N$ is of the form $4k+3$, there ...