# 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, quadratic number fields and other related topics which may be treated in first courses on number theory. More advanced topics should instead use the number-theory or other tags.

35,757 questions
Filter by
Sorted by
Tagged with
36 views

### Amount of compositions until $f(x)=x-\lfloor\frac{x}{n}\rfloor$ becomes constant

Suppose I have positive integers $a$ and $n$. I want to find the number of times $f(x)=x-\lfloor\frac{x}{n}\rfloor$ could be composed on itself with initial argument $a$ until a number less than $n$ ...
31 views

### Why is $2^{-1}$ (mod 13) equal to 7 while $2^{12}$ (mod 13) equal to 1 [duplicate]

I thought that $\!\bmod p\!:\, {-}1\equiv p-1$? Isn't $\,{-}1\equiv 12 \pmod{\!13}$ and why would exponentiation change that?
50 views

### Why is the remainder when $8^{43}$ divided by seven not obtainable by the cycle of four in the units digit when eight is powered? [duplicate]

What is the remainder when $8^{43}$ divided by seven? $8^{43}=2^{120+9}$ the units digit of $2^x$ cycles in lengths of four from $2,4,8,6$ $4 \cdot 32=128$ 32 cycles of four ended, and we return to ...
• 103
1 vote
40 views

### Similarity of Lifting the Exponent Lemma in Pell numbers

Pell number is a term of the sequence $\{P_n\}$ determined by a recurrence relation $$P_{n+2}=2P_{n+1}+P_n, P_0=0, P_1=1.$$ Let $v_p(x)$ be the $p$-adic valuation of an integer $x$ (the number of ...
• 145
1 vote
14 views

### Reinforcement of the Gauss Lemma (the one about quadratic reciprocity law) [closed]

Let $a$ be a positive odd number. $b \in \mathbb{Z}$, s.t. $gcd(a,b)=1$ Assuming $\left\{ r_i \right\}_{i=0}^{a-1}$ s.t.$r_i \equiv bi (\mod a)$,$-\frac{a}{2}<r_i<\frac{a}{2}$ $n$ is the ...
• 11
21 views

### Find the maximum difference between consecutive integers with the most and the least divisors of interest

Suppose that $a$ is a set of integers with each element $a[i] \ge 2$, and any 2 integers in this list are co-prime. Any $k$ consecutive integers will contain a certain number of integers that divides ...
32 views

### How to prove that $(4n + 3)$ and $(20n + 23)$ are mutualy prime? [duplicate]

Following the next theorem: $$\gcd(a; b) = \gcd(a - b; b)$$ I get to the point where from these two numbers $4n + 3$ and $20n + 23$ I get these: $4n + 3$ and $8$. It seems obvious that these numbers ...
• 101
1 vote
20 views

• 7,819
1 vote
22 views

### Given $ax=by, a(m^2+n^2)=b(p^2+q^2), (a,b)=(x,y)=1$, show that $a,b$ must also be sums of two squares. [duplicate]

I'm asking for verification of the following proof: We start with the following equality, working entirely in $\mathbb{Z}$: $$a(m^2+n^2)=b(p^2+q^2)$$ With $x=m^2+n^2,y=p^2+q^2; a,b$ coprime and $x,y$ ...
• 2,506
36 views

### A problem involving prime numbers and them dividing some function of themselves. [closed]

A friend sent me this question. This is I guess a previous year question of some Olympiad. I don't know to approach it. Any small idea that will get me started on this problem will be very helpfull. I ...
31 views

• 71
36 views

### $\mathbb{Z}[(1+\sqrt{-19})/2]$ is PID [duplicate]

I am reading Dummit & Foote's book and on page 282, I can't understand the part that I have offset and bolded in the following quote. How can we conclude that $ay-19bx=cq+r$? I know that there is ...
• 133
1 vote
43 views

### Name for integer "quotient" rounded up (ceiling) instead of down (floor), and its negative or complementary "remainder"

If $168$ cookies (dividend) are shared between $17$ people (divisor), that's almost $10$ cookies each but we're $2$ cookies "short"; alternatively we have slightly more than $9$ cookies each ...
• 1,327
126 views
+50

• 16.3k
49 views

### Given $n$ not prime, is there always a $1<k<n$, such that $n \nmid \binom{n}{k}$?

My kid shared something from internet on Pascal's triangle that, if $p$ is a prime, then for the $p$-th row, except the beginning and ending $1$, each number is divisible by $p$. This is, of course, ...
• 4,731
1 vote
69 views

### Sum of co-primes of a number $n \le k$

Problem Given a number $n$ and a number $k$ ($k\leq n$) we are to find sum of co-primes of $n$ less than or equal to $k$ My thoughts factorise $n$ and then do $k(k + 1)/2$ - ...
79 views

### Why is $f(x)\equiv f(x+2k)\pmod k$ for$f(x)=x(x+1)/2 + c.$

I came across this in a programming contest: f(x)%k = f(x+2k)%k for f(x)=x(x+1)/2 + c I first thought that this is a property of Harmonic numbers only but after ...
• 453
46 views

### When can two integers of this form be said to belong to the same set?

If I have two numbers $a_1$ and $a_2$ of the form: $$a_1=b_1 C+d_1\mod E$$ and $$a_2=b_2 C+d_2\mod E$$ where I know $C$ and $E$ but $b_1$ and $b_2$ are arbitrary positive integers. Under what ...
68 views

### Find a good starting point to search for $n$ consecutive composite numbers.

I'd like to use the Prime Number Theorem (PNT) to find a good starting point to search for $n$ consecutive composite numbers. The PNT says For large enough $x$, the probability that a random integer ...
• 1,253
87 views

### How to prove the existence of a Pythagorean Triple without finding solutions?

I am looking to prove that there is a Pythagorean Triple (x, y, 173) without finding solutions. I know that a solution does exist ((52, 165, 173)), however I would like to prove this more generally (...
• 183
50 views

### Sufficiently large prime numbers $6z + 1$ are not all of the form $36xy - 6x + 6y + 1$ for $x,y \neq 0$?

The polynomial $36xy - 6x + 6y + 1$ seems to be irreducible over $\Bbb{Z}$ or even $\Bbb{Z}[i]$. I don't know if that matters, but, I don't think all large enough primes of the form $6z + 1$ can &...
• 19.8k