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

Questions tagged [elementary-number-theory]

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

0
votes
0answers
10 views

Compositeness tests for numbers of the form $k \cdot b^n \pm c$

Can you provide proofs or counterexamples for the following claims? Claim 1 Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $M= k \cdot b^{n}-c $ where $k,b,n,c$ are ...
1
vote
0answers
18 views

Prove there are infinitely many positive whole numbers that are NOT of the form $4xy+3x+y$ or $4xy+3x-y$

Problem: Prove that there are infinitely many positive integer numbers that can't be written as $4xy+3x+y$ OR $4xy+3x-y$, where $x,y$ are positive integers, and $y$ can be zero, too. I tried ...
1
vote
1answer
31 views

Can the set of odd primes be decomposed into $\Bbb{P} = A + B, $ for some $A,B \subset \Bbb{Z}$?

Can there ever exist infinite sets of integers $A, B$ such that $A + B = \{ a + b: a \in A, b \in B\} = \Bbb{P}$? Where $\Bbb{P}$ is the set of odd primes? You can include $0$ and / or $\pm$ odd ...
0
votes
0answers
22 views

Three runners start at different speeds, two at 7:00am, one a 7:01am

Three runners called them Tom, Dick and Harry run along a circular route. Tom takes 5 minutes to complete a round, Dick takes 7 minutes, and Harry takes 11 minutes. Tom and Harry start their run at 7:...
3
votes
4answers
40 views

Why is $|x|$ defined as $\sqrt{x^2}$ instead of $(\sqrt{x})^2$?

I can't seem to understand this even though it might be utterly simple for some people. For me, saying $|x|=\sqrt{x^2}$ is a bit weird since $\sqrt{x^2}$ doesn't force positivity as there are always ...
2
votes
1answer
28 views

Proving Euler-Fermat's Theorem

I am trying to prove that if $g.c.d.(a, m) = 1$ then $a^{\phi(m)} \equiv 1 (\textbf{mod }m). $ I have defined the following sets: Let set $\textbf{A}$ be the set of prime integers $<$ m Let set $...
2
votes
2answers
37 views

“Although it is necessary for $n$ to be prime in order for $R_n$ to be prime” as logic statement

This is a statement about Repunits from this paper. How can I write this as an if/then statement? Knowledge about Repunits isn't required. The question is basically: what does "although it is ...
2
votes
1answer
27 views

Can you determine small primes from larger primes?

Suppose you are given the primes in the range $[n,n^2]$. Is there a known way to effectively reconstruct the primes less than $n$? Ideally, something that takes less calculation than figuring them out ...
2
votes
1answer
32 views

Does this follow from congruence?

Let a and b be two distinct prime numbers and x and y are integers. Is the following true? ($x \equiv y \mod a$) and ($x \equiv y \mod b$). So, $a|(x-y)$ and $b|(x-y)$. This means $x-y=ab\phi$ with $\...
1
vote
3answers
31 views

The cube of any integer divided by 8 leaves a remainder?

Here's my approach, Let $a \in \mathbb{Z}$, from division algorithm, therefore $a$ is of the form of $ 8k + r, \, 0≤r<8$ I then obtained $8$ cases from this, and cubed all of them, factored $8$ ...
1
vote
1answer
24 views

Trying to understand a lemma in a math paper on LCM

Through Wikipedia, I discovered the following Arxiv.org article on Least Common Multiple. I have not seen the notation referenced and I am not clear how $\gamma$ is defined since it stated to be a ...
0
votes
2answers
43 views

Prove (in)equivalency: (1) $\exists$ non-zero $z\in\mathbb{Z}/n\mathbb{Z}$ such that $z^{t}=0$ for some $t$, (2) $\exists$ prime $p$ such that $p^2|n$

I need to prove the equivalency/inequivalency of two statements: (1) There exists a $z \in \mathbb{Z}/n\mathbb{Z}$, $z\neq{0}$, with $z^{t} = 0$ for some $t \in \mathbb{N}$ (2) There exists a prime ...
0
votes
0answers
15 views

Is there a equality or upper bound for the least common multiple of all consecutive even/odd numbers?

It's know that if $(1,2,3,...,n)$ is a sequence of consecutive natural numbers and $p^j$ is the greatest power of a prime $p$ that doesn't exceed $n$, then \begin{equation} LCM(1,2,3,...,n) = \prod_{p ...
1
vote
1answer
32 views

Number repositioning

You are given $2^n$ numbers, in one step you move the numbers in odd positions to the beginning of the list and the numbers in even positions to the end of the list, keeping the initial order among ...
2
votes
0answers
41 views

Reasoning about the lower bound of ${{2n}\choose{n}}$

A standard lower bound is ${{2n}\choose{n}} > \frac{4^n}{2n}$. For example, see this Wikipedia article. It occurs to me that for higher $n$ using elementary arguments, this can be greatly ...
1
vote
1answer
28 views

let p be a prime number such that {p = 3 [4]} show that the equation {x ^ 2 + 1} = {[p]} does not admit solutions in Z [duplicate]

let p be a prime number such that {p = 3 [4]} show that the equation {x ^ 2 + 1} = {[p]} does not admit solutions in Z
3
votes
3answers
26 views

Why do we eventually end up with $0$ in Euclidean Algorithm?

I'm new to number theory, I just understood the proof of Euclidean Algorithm and how it cleverly uses the fact that $\mathrm{gcd}(a,b) = \mathrm{gcd}(b,r)$ repeatedly, where $a$ is the dividend, $b$ ...
4
votes
1answer
39 views

Find all values of $n, m \in \mathbb{Z^+}$ where ${n \choose m}=1984$

Find all $n, m \in \mathbb{Z^+}$ where ${n \choose m}=1984$ I tried so hard on this question in the past couple of days I couldn't achieve anything, which forced me to resort to the guess and check ...
1
vote
3answers
69 views

Prove that gcd$(n^2+1, (n+1)^2+1)$ is either 1 or 5

My try to solve this question goes as follows: $g=gcd(n^2+1, (n+1^2)+1) = gcd(n^2+1, 2n+1) = gcd(n^2-2n, 2n+1)$. By long division: $$n^2-2n = -2n(2n+1) + 5n^2$$ Since $g$ divides $n^2-2n$ and $g$ ...
6
votes
1answer
65 views

Prove that $q^i \equiv 1 \pmod {n!}$ for all $q, n \in \mathbb{Z^+}$ where the prime factors of $q$ are greater than $n$

The question originally states: Let $n$ and $q$ are positive integers, such that all prime divisors of $q$ are greater than $n$. Show that $$(q-1)(q^2-1)(q^3-1)...(q^{n-1}-1) \equiv 0 \pmod {n!}$$ ...
1
vote
1answer
39 views

Solution of $X^2+Y^2=Z^2$

As we know before the general solution of the equation $x^2+y^2=z^2$ in the number theory is as follows: $x=\pm(a^2-b^2)c$, $y=\pm 2abc$ and $z=\pm(a^2+b^2)c$. I want to know how to find a solution ...
2
votes
3answers
67 views

There are two irreducible rational numbers with denominators 600 and 700. Find the minimal possible value of the denominator of their sum.

The question states: There are two irreducible rational numbers with denominators $600$ and $700$. Find the minimal possible value of the denominator of their sum. I tried to rearrange it into $$\...
0
votes
2answers
30 views

Prove that if $n>1$, the sum of positive integers less than $n$ and coprime to $n$ is $(1/2)na(n)$ where $a(n)$ is the number of such integers. [duplicate]

Question 12(iii) Could anyone explain this part of the question to me. What i tried co-prime means that the two integers a and b are said to be relatively prime, mutually prime, or coprime (also ...
0
votes
6answers
76 views

Give a proof by cases that shows that $n(n ^2 − 1)(n + 2) $ is a multiple of $4$, for all integers $n$ [duplicate]

Give a proof by cases that shows that $n(n ^2 − 1)(n + 2) $ is a multiple of $4$, for all integers $n$ I have already done case 1 where n is even. I am doing case 2 where n is odd and I'm a bit ...
0
votes
1answer
15 views

Hamming distance function for bits is an injective or surjective function?

Let's say we have d: T8 x T8 -> {0,1,2,3,4,5,6,7,8} $$d(a,b) = \sum_{i=1}^8 ai \oplus bi $$ Where a1 is the bit a that is at position i and bi and the bit b that is in position i. Would this be an ...
0
votes
0answers
20 views

If $(x,y)=1 $ then $ (tx+y,n)=1$ [duplicate]

Prove that if $(x,y)=1$ than for all $n \in N$ exist $t \in N $ such that $$(tx+y,n)=1$$ I think this result is true because it follows from Dirichlet's theorem, although there must be an elementary ...
5
votes
0answers
54 views

Show that the equation $x^2+y^2+z^2=2xyz$ has no integer solutions except $x=y=z=0$ using modular arithmetic [duplicate]

(a) Using modular arithmetic Show that the equation $$x^2+y^2+z^2=2xyz$$ has no integer solutions except $x=y=z=0$ (b) Using the results in part (a), show that the equation $$x^3+2y^3+4z^3=0$$ has ...
2
votes
3answers
72 views

Factor $10^6-1$ completely

I know kind of a very elementary method to factor this number. Consider the following: $$10^6-1 = (10^3-1)(10^3+1)=9 \times 11 \times (10^2+10+1)(10^2-10+1) = 9 \times 11 \times 111\times 91$$ I would ...
0
votes
1answer
80 views
+50

Compositeness tests for generalized repunit numbers

Can you provide proofs or counterexamples for the following two claims: First claim Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $M_p(a)= \frac{a^p-1}{a-1} $ where $a$ ...
5
votes
2answers
418 views

Finding the leading digit(s) in any number

I am somewhat perplexed by this (presumably very simple) issue. Simply, I am trying to find the leading digit(s) in any number (related question). Here is some nice python code (from this question): ...
-1
votes
2answers
50 views

Bezout identity of 720 and 231 by hand impossible? [duplicate]

Is it possible to solve this by hand? Without using the Extended Euclidean Algorithm We do the Euclidean algorithm and we get: 720 = 231 * 3 + 27 231 = 27 * 8 + 15 27 = 15 * 1 + 12 15 = 12 * 1 + ...
0
votes
0answers
22 views

Prove the summation of euler function for divisors of g

Given that the Euler function is $\phi(p_i)=p_i^{a_1}-p^{a_i-1}$ for prime $p$ prove that $c=\sum_{b>0,b|c} \phi(b)$ My work so far: from the summation we want all b that divides c, so we write c ...
1
vote
1answer
28 views

What is the least residue of 49^4 modulo 23 [duplicate]

This is what I got so far but for some reason I feel like I am wrong. 49 is congruent to 26 mod(23). Therefore we have 49^4 is congruent to 26^4 = 456976 which is congruent to 456923 mod(23)but this ...
-1
votes
0answers
35 views

Egyptian fraction books

Can you tell name good books about proof of Egyptian fractions? I did not find books about egyptian fractions in my country. I need this books because I want proof Erdos-Struss conjecture. I read ...
3
votes
1answer
64 views

Not clear in one step in the inequality for the proof LCM$(1,2,\dots,n) < 3^n$

I believe that I am following Hanson's proof up until this point (page 36): $$C(n) < \dfrac{(en)^{k-1+1/(a_{k+1}+1)}w^n}{(a_1)^{(a_1-1)/a_1}(a_2)^{(a_2-1)/a_2}\dots(a_m)^{(a_k-1)/a_k}}$$ where $...
0
votes
3answers
32 views

Finding X for Mod?

If I have this: $x \pmod p = 1$ $x \pmod q = 0$ Is there any way I can find a possible natural number for $x$ that satisfies both equations. I know it has something to do with the Chinese Reminder ...
1
vote
3answers
43 views

Dividing $n^k+1$ by $n+1$ if and only if $k$ is odd

For that question, I can use modular arithmetic to prove divisibility. Look at the following: $$n \equiv-1\mod(n+1)$$ raising to $k^{th}$ power, if $k$ is odd, then $$n^k \equiv(-1)^k \equiv-1\mod(n+1)...
-1
votes
2answers
37 views

Prove that if a ^ 2 ≡ b ^ 2 (mod p), then a ≡ ± b (mod p). [on hold]

hello could help me with this problem I used a theorem but I do not know if esat well
1
vote
2answers
31 views

For polynomials $f, g$ and $\gcd(f(X),g(X))=d(X)$ then $\gcd(f(X+a),g(X+a))=d(X+a)$

Suppose for polynomials f, g in $\mathbb{Q}[X]$ it holds that $$\gcd(f(X),g(X))=d(X)$$ What we also want to now prove is that for $a \in \mathbb{Q}$: $$\gcd(f(X+a),g(X+a))=d(X+a)$$ So the ...
1
vote
2answers
35 views

Generating Pythagorean triples

I'm asked to generate Pythagorean triples from the polynomial identity: $$(X^2-1)^2 + (2X)^2=(X^2+1)^2$$ By substituting rational numbers $\frac p q$ for $X$. However, Pythagorean triples are just as ...
2
votes
0answers
62 views

Find all positive integers $a, b, c$ such that $(a^{3}+b)(b^{3}+a)=2^{c}$. [duplicate]

Find all positive integers $a, b, c$ such that $(a^{3}+b)(b^{3}+a)=2^{c}$. I tried considering the prime factorization of both sides and using the exponent of 2 in it: $$v_{2}(a^{3}+b)+v_{2}(b^{3}+a)=...
0
votes
0answers
18 views

Divisibility of the sum $S$ of the self-convolution of the divisors of $n$

Start at 2 and all following composites to find the sum S of the divisors of n when they are convolved with themselves. (a)For 39 the divisors are 1, 3, 13, 39 and the sum S=$(1*1) + (3*1+1*3) + (...
1
vote
0answers
68 views

Did I find a mistake in a classic proof? If not, could someone help me understand?

I am working through Denis Hanson's proof that LCM$(1,2,3,\dots,n) < 3^n$ To be clear, the mistake is minor and does not affect the result achieved. Still, I was surprised. Here's what I believe ...
-4
votes
1answer
25 views

Proof by simple induction, summation [on hold]

https://imgur.com/a/U3ZjKfT How do I continue with this proof by induction? I recognize that I want to get my answer to the heading labeled under IC, but I don't see a way to continue. Or, did I ...
2
votes
0answers
30 views

Prove that any polynomial with integer coefficients must have a composite number in its image. [duplicate]

Let $f \in \mathbb{Z}[x]$ be a polynomial of degree at least $1$. Prove that there is $n \in \mathbb{Z} $ such that the corresponding polynomial function $f(n)$ is not a prime. I think that the ...
1
vote
0answers
41 views

Generating prime factors of a certain congruence?

I'm aware that prime factors of $n^2+1$ take the form $4k+1$. It's also well known that factors dividing $\frac{a^p \pm 1}{a \pm 1}$ will be congruent to $2kp+1$. Fibonacci and some other recurrence ...
7
votes
1answer
76 views

The term “remainder” and IMO 2005, problem 2

I was looking at IMO 2005, problem 2: Let $a_1, a_2, . ...$ be a sequence of integers with infinitely many positive terms and infinitely many negative terms. Suppose that for each positive integer $n$...
2
votes
1answer
32 views

Primes congruent to $k \pmod p$ between $p$ and $p^2$?

Is it true that for any prime $p$, there are primes $< p^2$ which are congruent to every $k<p$? For example, $$ \begin{align} 11 &\equiv 1 \pmod 5 \\ 7 &\equiv 2 \pmod 5 \\ 13 &\...
0
votes
0answers
21 views

Numeralwise expressibility in logic

I am reading Chapter 8 Section 41 of Kleene's "Introduction to metamathematics" and I have encountered notion of "numeralwise expressibility". Next is a quote from the textbook: "Let $P(x_1, ..., x_n)...
0
votes
0answers
26 views

RSA repeated exponentiation

I am trying to prove that in RSA, if choose any number $M < n$ and repeatedly calculate the exponentiation repeatedly i.e. $M^1 \bmod n, M^2 \bmod n,\cdots,M^i \bmod n,\dots$, it will generate ...