Questions tagged [elementary-number-theory]

Questions on divisibility, gcd and lcm, congruences, linear Diophantine equations, Fermat's and Wilson's theorems, the Chinese Remainder theorem, primitive roots, quadratic congruences, and other related topics in the early study of number theory. More advanced topics should receive the number-theory tag instead.

Filter by
Sorted by
Tagged with
1
vote
0answers
8 views

Maximize sums of products via permutation

Let $A = [a_0, a_2, ..., a_{n-1}]$ and $B = [b_0, b_1, ..., b_{n-1}]$ be two array of positive real numbers. Find a permutation $\pi$ of $A$ which maximizes the following sum $$\sum_{i = 0}^{n-1}a_{\...
2
votes
0answers
60 views

An integer n >= 2 is called square-positive- proof?

An integer n >= 2 is called square-positive if there are n consecutive positive integers whose sum is a square. Determine the first four square-positive integers. So I have found the first four ...
0
votes
2answers
43 views

Determine $(m,n,k)$ such that $P(m,2)=P(n,k)$

The permutation of $r$ objects from a given group of $n$ is calculated by the permutation function defined as: $P(n,r)=\frac{n!}{(n-r)!}$. Find a general method (other than brute force programming) ...
3
votes
1answer
72 views

Show that there are infinitely many primes $p$ with $p^5 \equiv 5 \pmod 6$ [duplicate]

Show that there are infinitely many primes $p$ with $$p^5 \equiv 5 \pmod 6$$ I am very confused by this question. I am familiar with Euclid's proof of there being infinitely many primes and can see ...
1
vote
1answer
65 views

Them four primes

This is not a problem from any text, but a curiosity into the pattern of prime numbers. It is known that 11, 13, 17, 19 are primes. It is also known that 101, 103, 107, 109 are primes. Is there any ...
0
votes
0answers
57 views

Find the number of solutions to $x^3 \equiv x \pmod n$

Rephrasing the question, it is asking to find the number of solutions to $n|x(x+1)(x-1)$ What I have so far is that if $n$ is prime then the solutions are $x = 0, 1, n-1$, and for $n$ is composite I ...
0
votes
1answer
29 views

Prove that there exist arbitrarily long sequence of consecutive integers not of the form $x^k$ with $k > 1$. (Assuming that $x \in \mathbb Z$)

I'm not sure how to approach this question exactly, I've thought about assuming that the length of the sequence is finite and bounded above and somehow construct a contradiction. Any hint on how to ...
-1
votes
2answers
36 views

Find $x \equiv 7^a-2 \pmod {55}$

Find the values of $x$ if $$7^a-2 \equiv x \pmod {55}$$ and $a=40k$, where $k$ is an integer. I am not entirely sure of how to approach this problem. So, please post hints and not the entire solution....
0
votes
0answers
27 views

Using Hensel's Lemma to find the number of elements satisfying a congruence

My problem is really a conceptual one, rather than a specific one, but I'll provide an example question to illustrate where my difficulty lies. This is in an exercise set provided by my professor. ...
2
votes
1answer
47 views

Primes 5 mod 8 can be written in the form $(2x+y)^2 + 4y^2$

I am stuck trying to prove the theorem using an algebraic approach, please could someone give me a hint(preferably not the whole answer) Primes 5 mod 8 can be written in the form $(2x+y)^2 + 4y^2$ I ...
0
votes
0answers
38 views

Question in Chapter -12 Apostol's Number Theory (Vol 1)

I am trying some exercises from Apostol's Introduction to ANT and I need help in solving question 12 part d(page 275). Unfortunately, I don't have any ideas on which result should I use here. Just ...
0
votes
3answers
31 views

Proving an argument regarding divisibility to be used in another question. [duplicate]

This particular argument was to be used in another question which I am trying. If $a,b$ are integers with $a\geq $2 and $b\geq 2 $ and $ab>4$, prove that $ab$ divides $(ab-1)!$. I have proved ...
1
vote
0answers
26 views

2-adic valuation of $5^{2^{k-2}}$

I have the following exercice : Consider that the 2-adic valuation of x is k $\geq$ 1. Prove that the 2-adic valuation of $(1+x)^2$ - 1 is k+1 Using the previous question, conclude that for k $\geq$ ...
1
vote
0answers
72 views

A question about understanding the proofs for $x^3+y^3=z^3$

The problem is prove $x^3 + y^3 = z^3$ has no positive integer solutions. I understand this was proven in the 1700s by Euler, but I cannot find any books or in-depth references on the proof. Here are ...
2
votes
0answers
29 views

Proving that GCD of $3$ numbers is same as the GCD of GCD of $2$ numbers and the third. [duplicate]

Here's the problem: This problem looks so trivial at staring, but rigorously proving it turns out to be difficult task for me. I know of $2$ ways of defining GCD (of, say $b$ and $c$): The least ...
-1
votes
2answers
79 views

Calculating the gcd of $6-7i$ and $2-9i$

I need help in calculating the gcd of complex numbers $6-7i$ and $2-9i$. The problem is I don't know the algorithm for complex numbers and I've read a few posts related to this but it seem like it ...
0
votes
1answer
26 views

How many different possible remainders of a square number modulo an odd prime?

Here is a solution to the question: I get it up to 'This means that either x-y = 0 ...' Beyond that, I am very confused. I was wondering if someone more experienced could clarify the remaining ...
0
votes
3answers
41 views

Assume that $ab \mid (a+b)^2.$ Show that $ab \mid (a-b)^2$.

Assume that $ab \mid (a+b)^2.$ Show that $ab \mid (a-b)^2$. If $ab \mid (a+b)^²$, then $ab\mid a^2+2ab+b^2 \Longrightarrow ab\mid a^2, ab\mid 2ab$ and $ab\mid b^2$ right? So since $(a-b)^2 = a^2-2ab+...
5
votes
3answers
97 views

Last digit in $\sum_{k=1}^{999}k^m$ (olympiad question)

I'm trying to prepare myself for mathematics olympiad. I faced a problem which is kind of interesting, here is the question: Oleg chose a positive integer like $m$ and Andrew found the following ...
0
votes
0answers
32 views

Euclid's Theorem via Sieve of Eratosthenes? (potential proof given but seeking references/alternatives/verification)

There is a tantalizing reference to a proof of Euclid via Eratosthenes referenced in this paper, reference 139. However, that reference was posted on a now-defunct internet forum, and the Wayback ...
3
votes
0answers
60 views

$\lfloor x^n\rfloor\lfloor y^n\rfloor$ is a perfect square

Let $x,y\ge 1$ be non-integer real numbers such that $\lfloor x^n\rfloor\lfloor y^n\rfloor$ is a perfect square for any natural number $n$. Does it follow that $x=y$? From this question we know the ...
4
votes
1answer
72 views

Why are repeating decimals often self-inversions?

Let $b$ be any base, and let $x$ be some odd integer. Empirically, it seems that for any $b$, the majority of odd $x$ will have the following property. Given a reptend $r$ with $2k$ digits as in $$\...
3
votes
2answers
49 views

Prove that every prime number greater than 3 is either one more or one less than a multiple of $6$ [duplicate]

Prove that every prime number greater than 3 is either one more or one less than a multiple of $6$. (Hint: Consider the contrapositive by cases.) I tried this problem using contrapositive but It is ...
0
votes
1answer
31 views

Prove existence and uniqueness of m-adic representation of any natural number [duplicate]

I have come across a problem in an elementary mathematics book that I am seeking help with. The problem states : "Given $m,n \in \mathbb{N}$, with $m > 1$, prove that there exist unique ...
-3
votes
2answers
47 views

Is Euler's totient function surjective? [duplicate]

I other words can i find a number m for any number n such that φ(m)=n? It would be great if you could also present a proof or a link to a paper that contains a proof Edited note: I forgot to mantion n ...
1
vote
2answers
47 views

A relation between the GCD and LCM of 3 numbers [duplicate]

Prove: $\frac{[a,b,c]^2}{[a,b][b,c][c,a]} = \frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}$ Where $(a,b)$ and $[a,b]$ represent GCD and LCM respectively Let $(a,b,c) = q$ $a = qp_1$, $b = qp_2$, $c=qp_3$, $(p_1,...
1
vote
2answers
44 views

Can the number of terms of sequence $p_1$, $2p_1+1$, $2(2p_1+1)+1$, . . . be more than 3?

Can the number of terms of sequence $p_1$, $2p_1+1$, $2(2p_1+1)+1$, . . . be more than 3? Where all terms are prime. For primes $p_1\equiv 1 mod 3$ we have: $2p_1+1\equiv (2+1) mod 3 \equiv 0 mod 3$ ...
1
vote
0answers
61 views

If $P$ is a finite set of primes, such that $\sum_P\frac{1}{p}>1$, express $max\{n\in\mathbb N_+ : \sum_P\Big\lfloor\frac{n}{p}\Big\rfloor<n\}$

As discussed here: Prove (or disprove) a correlation between a prime number subset and a maximum $n\in\mathbb N_+$, it is true that $$\sum_{P}\frac{1}{p} > 1 \Longleftrightarrow 0 < \#\{n\in\...
1
vote
1answer
28 views

Using GCD with remainder to list all the integer elements in the set

My question is: For an integer k, define $f(x) = gcd (13x + 2, 5x − 1)$, use GCD With Remainders to list all the elements in the set ${f(x): x ∈ Z}$. I divided 13x+2 by 5x-1 first, and got a quotient ...
0
votes
1answer
58 views

Solve $6x\equiv 2\pmod 8$ [duplicate]

Solve $6x\equiv 2\pmod 8$ This is the method that I used: $$6x\equiv 2\pmod 8\implies12x\equiv 4\pmod 8\implies3x\equiv 1\pmod 8\implies9x\equiv 3\pmod 8$$ $$\implies x\equiv 3\pmod 8$$ However, the ...
0
votes
1answer
47 views

Let $p$ be a prime number. Prove there exists an integer $a$ such that $p\mid (a^2-a+3)$ iff there exists an integer $b$ such that $p\mid(b^2-b+25)$. [duplicate]

Let $p$ be a prime number. Prove that there exists an integer $a$ such that $p\mid(a^2-a+3)$ if and only if there exists an integer $b$ such that $p\mid(b^2-b+25)$. I'm getting a bit confused with ...
2
votes
2answers
65 views

What is the remainder left after dividing $1!+2!+3!…+100!$ by $6$? [closed]

Just came across this question today. I wonder how to solve this as it is a factorial question.
1
vote
1answer
42 views

Is it true that $\frac 1q=\sum\limits_{\text{prime }p}^{\infty}\frac{1}{q^{p-1}-1}$ for all $q\notin[-1,1]$?

I believe I have proved that, for all $q\notin[-1,1]$, it follows $$\frac{1}{q}=\sum_{\text{prime }p}^\infty\frac{1}{q^{p-1}-1}$$ Of course this is a huge result, so I want to see if my proof is ...
-3
votes
4answers
65 views

solving $3x^2 +4x-2= 0\pmod{31}$ [duplicate]

I tried multiplying both sided by 4a which leads to $(6x+4)^2=40 \pmod{372}$ now I'm stuck with how to find the square root of a modulo.
0
votes
3answers
48 views

$a^b+b^c+c^a$ is a multiple of 8 if and only if $a+b+c$ is multiple of 8

Let $a, b, c$ are odd natural numbers. Is "$a^b+b^c+c^a$ is a multiple of 8 if and only if $a+b+c$ is multiple of 8" right? I don't know how to begin, please help me.
-1
votes
0answers
12 views

Proof of a theorem involving relatively prime integers and modular congruence [duplicate]

Let r and m be relatively prime integers, with m>1. If a and b are integers for which ra = rb (mod m), then a = b (mod m). How do I prove this theorem? I'm thinking it's helpful to view it in terms ...
-1
votes
3answers
47 views

Find all positive integers $a$ such that $ax \equiv 1$ (mod 24) has integer solutions

Through general experimentation I've found that there seem to be solutions for $a = 1 + 6n$ and $a = 5 + 6n$, but I don't know how I'd go about actually proving that this pattern holds forever (...
3
votes
1answer
52 views

Prove (or disprove) a correlation between a prime number subset and a maximum $n\in\mathbb N_+$

I'm kind of testing my own observation that I came up with but may very well have already been worked on. I basically try to find a correlation between the following two: Let $P = \{p\in\mathbb N_+ | ...
2
votes
6answers
99 views

Let $n$ be an integer. If the tens digit of $n^2$ is 7, what is the units digit of $n^2$?

Let $n$ be an integer. If the tens digit of $n^2$ is 7, what is the units digit of $n^2$? So $n^2 \equiv 7 \pmod{100}$? If this is the case then this can be written as $n^2 = 100k +7$, where $k \in \...
0
votes
1answer
84 views

Diophantine question: find two positive numbers a and b such that $a\cdot b+a=c^3$ and $a\cdot b+b=d^3$

Diophantine question: find two positive numbers a and b such that $a\cdot b+a=c^3$ and $a\cdot b+b=d^3$ I solved this equation , the solution are rational; $\frac{112}{13}$ and $\frac{27}{169}$. Can ...
0
votes
5answers
45 views

Prove that if $p$ and $p+2$ are both prime integers greater than $3$, then $6$ is a factor of $p+1$. [duplicate]

Prove that if $p$ and $p+2$ are both prime integers greater than $3$, then $6$ is a factor of $p+1$. Computing a few primes greater than $3$ modulo $6$ shows the following pattern $5,1,5,\dots$ Thus $...
0
votes
0answers
40 views

Name of the formula for divisibility of factorials

Suppose we want to find how many factors of $7$ is in $500!$. We want to find number of factors of $7$ in $N = 500 \cdot 499 \cdot ... \cdot 7 \cdot ... \cdot 2 \cdot 1.$ Of course, we can eliminate ...
0
votes
0answers
29 views

Proving a relation between sum of reciprocal of divisors and $\sigma(n)$

Prove that $\sum_{d\mid n}\dfrac{1}{d}=\dfrac{\sigma(n)}{n}\ \forall\ n\geq 1, n\in \mathbb Z$ My question and my approach is a lot similar to this question and a bit different from this question ...
0
votes
0answers
48 views

$n!+1$ is composite for infinitely many odd $n$

It's the number theory problem from Thailand Mathematical Olympiad. That require one to prove that $n!+1$ is composite for infinitely many odd $n$. It's true if $n$ is even from Wilson's theorem ...
0
votes
1answer
27 views

Prove that for all natural numbers $k$, $k^5-k$ is a multiple of $10$. [duplicate]

Prove that for all natural numbers $k$, $k^5-k$ is a multiple of $10$. I found several answers for this here, but none of which would have considered seperately the cases $\pmod{2}$ and $\pmod{5}.$ ...
1
vote
1answer
20 views

Let $x$ and $y$ be integers such that $2x+3y$ is a multiple of $17$. Show that $9x+5y$ must also be a multiple of $17$. [duplicate]

Let $x$ and $y$ be integers such that $2x+3y$ is a multiple of $17$. Show that $9x+5y$ must also be a multiple of $17$. So $2x+3y \equiv 0 \pmod{17}$. Adding $7x$ and $2y$ we have that $9x+5y \equiv ...
1
vote
2answers
62 views

Most efficient solution to find polynomial congruence for 0 mod p

I was given the polynomial $$f(x) = x^4 + 2x^3 + 3x^2 + x + 1$$ and told to find $$f(x) \mod 17 = 0 $$ I found the solution to be $$x = 8 + 17n$$ However, I arrived at this solution by computing all ...
0
votes
1answer
42 views

Verifying associativity of monoids using number theoretic argument

I'm studying monoids and trying to test whether a given construction is a monoid. Given a set $M=\{x_0, x_1, ..., x_6\}$ and a multiplication $x_i \cdot x_j = x_{i+j-k}$ where $k$ is the largest ...
1
vote
1answer
32 views

Values of the expression $ax \pmod b$ as a function of $x$

I'm trying to better understand behavior of the expression $(ax\pmod b)$ as a function of $x \in \Bbb N$. Both constant numbers $a \in \Bbb N$ and $b \in \Bbb N$, and also we can assume that the ...
-4
votes
1answer
70 views

Can this be true that $3\mid 4 p+1$ for the majority of primes p? [closed]

Let p be a prime. Can this statement be true that for the majority of primes $3\mid 4p+1$, if so why? I checked this up to the first $23$ primes and it needs to be checked for very large amount. $2\...

1
2 3 4 5
620