Stack Exchange Network

Stack Exchange network consists of 175 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.

-1
votes
3answers
53 views

Find any 1-1 function from $\mathbb{Z}$ to $\mathbb{N}$.

I was thinking $f(n)=|n|$, but realized that would be a surjection. I'm not sure of how to solve this. Thank you.
1
vote
3answers
38 views

Solving Pell's Equation for $x^2 -7y^2 = 1$ for the first three integral solutions.

Like the title states my goal is the find the first three integral solutions of the Diophantine equation. I know $x^2 -7y^2 = 1$ is a Pell's equation where $d = 7$. I found the minimal solution to be $...
1
vote
1answer
44 views

Can I split this inequality like this?

Recently I had solved this number theory problem but after I solved it I was a bit uncertain whether my approach was correct so I approached AOPS. The problem is : Prove that $[x] + [y] + [x + y] \...
-4
votes
0answers
29 views

Three numbers game [on hold]

There is such a game. Three numbers are called. You can ask a question in three numbers, the answer is yes or no. It is necessary to guess the rule according to which these numbers can always be ...
6
votes
3answers
401 views

Why do all primes $n>3$ satisfy $\,309\mid 20^n-13^n-7^n$

Solve the following... $309|(20^n-13^n-7^n)$ in $\mathbb{Z}^+$. I invested lotof time to it and finally went to WolframAlpha for help by typing... Solve $309k=20^n-13^n-7^n$ over the integers. It ...
-1
votes
0answers
36 views

What could “sqrt 1 by 7” be interpreted as? [on hold]

A friend has been sending me puzzles in various forms and today I was given "sqrt 1 by 7" the moment I was writing an email, and added a bit of human touch to it. The goal of the game is to look at ...
1
vote
1answer
30 views

How to show that some elements of $\mathbb{Z}[2\sqrt{2}]$ are irreducible?

I want to show that $2$ and $2\sqrt{2}$ are irreducible in $\mathbb{Z}[2\sqrt{2}]$. Consider the norm $N:\mathbb{Z}[2\sqrt{2}]\to\mathbb{Z}_{\ge0}$ defined by $N(a+b\cdot2\sqrt{2})=a^{2}-8b^{2}$. ...
5
votes
2answers
55 views

Integer points on a surface

I would like to understand ${\bf nonnegative \ integral}$ solutions $(x,y,z)$ on the surface $$xyz-ax-ay-bz=d.$$ where $a,b,d$ are positive integers. I can certainly prove that for a fixed $z$ ...
1
vote
1answer
59 views

Find the smallest $n$ such that the $n$-th prime $p_n \equiv 330 \mod n $.

Find the smallest $n > 1$ such that the $n$-th prime $p_n \equiv 330 \mod n $. I was investigating the remainders when the $n$-th prime is divided by $n$. For every positive integer $a < 330$, ...
-4
votes
0answers
22 views

Cardinality/ pidgeonhole principle question [on hold]

Let A be a non-empty finite set, and $|A|=n$. How would I prove $|A\setminus\{a\}|=n-1$ if $a \in A$
2
votes
2answers
42 views

Show that a number $n$ is divisible by 6 if and only if it can be written as a sum of three distinct divisors.

If $6|n$ then $n=6k=3k+2k+k$. And $3k|n$, $2k|n$ and $k|n$. Now let $p,q$ and $r$ be three distinct divisors of $n$ so that : $$n=p+q+r$$ Because $p|n $, $ q|n$ and $r|n$ I figured that $p|q+r $, $ ...
3
votes
2answers
32 views

Proof that every common divisor divides GCD (solve only by Bézout's identity)

As part of the course's assignments, we received a task to prove the following sentence using only Bézout identity: Every common divisor of $a, b$ divides the gcd $(a, b)$. I tried the following ...
0
votes
0answers
40 views

Computing Integers' Prime Factorization Using the General Number Field Sieve

Recently, I have taken upon myself the task of writing an algorithm to compute the prime factorization of an integer. I am neither a mathematician nor a programmer/computers' engineer as an occupation,...
1
vote
1answer
28 views

Understanding Proof about Continued Fraction convergent sequences

I copied a proof from lecture and don't understand the end of it. It is intro number theory on continued fractions. Hopefully someone can explain it to me Background: The sequences {$h_n$} and {$k_n$...
-2
votes
1answer
42 views

Prove that if $p$ is a prime number and $n$ is a positive integer, then $\phi(p^n ) = p^n − p^{n−1 }$. [on hold]

Would I have to use Euler's phi function or the Euler Fermat theorem? Any help appreciated!
1
vote
1answer
68 views

How many positive integer solutions?

I'm interested in ${\bf integer}$ solutions of $$abcd+1=(ecd-c-d)(fab-a-b)$$ subject to ${\bf a,b,c,d \geq 2}$, and ${\bf e,f \geq 1}$. A few comments: (1) If $e,f \geq 2$ or $e=f=1$ then there ...
3
votes
0answers
63 views

Primality test for numbers of the form $N=k \cdot 3^n-1$

Can you provide proof or counterexample for the claim given below? Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following claim: Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(...
10
votes
2answers
153 views

can the product of four positive integers in A.P. be a square?

Title says it. It's known no four squares are in arithmetic progression, but it's asking less for their product to be square. I've tried various things like hunting to make each of two subproducts a ...
3
votes
1answer
47 views

Show that $\psi(n)$ has finitely many roots

Define $\psi(n)=\pi(n)-\phi(n)$ where we have the prime counting function and totient function respectively. I'm interested in where $\psi(n)=0$. Specifically is it possible to prove that there are ...
1
vote
0answers
36 views

Problem on largest prime divisor [duplicate]

For a positive integer $n$, let $p(n)$ the largest prime divisor of $n$. Show that there exist infinitely many positive integers m such that $p(m − 1) < p(m) < p(m + 1)$. Let $q$ be odd prime ...
0
votes
2answers
53 views

Proving $1+\sqrt2+\sqrt3$ is irrational [duplicate]

How can I prove that $1+\sqrt2+\sqrt3$ is an irrational number, without proving first $\sqrt2$ and $\sqrt3$ are irrational numbers? Please give some hints or suggestion to proceed with this proof. ...
-1
votes
2answers
59 views

All natural number solutions of the equation

Can you find all natural number solutions of this equation? I tried puting it in wolfram alpha and some other math problem solvers but they just solve it for one solution $$x = 2$$ and $$y = 1$$ $$y^{...
2
votes
1answer
43 views

Mapping $\mathbb{Z}_k$ into $\{d,d+1,\ldots,d+k-1\}$ preserving value $\bmod k$

I want to give a (simple) map $f:\mathbb{Z}_k \to \{d,d+1,\ldots,d+k-1\}$ for $d,k \in \mathbb{N}$ and such that $\forall i \in \mathbb{Z}_k. f(i) \bmod k = i$. Is there a particularly simple way ...
4
votes
0answers
82 views

Is there another pair of consecutive primes with this property?

Denote $$r(n)$$ to be the number that occurs if we reverse the digits of $n$ Suppose, $\ (p,q)\ $ is a pair of consecutive primes. The only prime $p$ with the property $$r(p)=2q$$ I found is $\ p=...
0
votes
2answers
52 views

An example of an even numbers $n,k$ whose $gcd$ is three.

I am looking for even integers $n$ and $k$ such that $k$ does not divide $n$ and $\gcd(n,k) = 3$. Is this possible? With the help of some online tools I tried, but every time I am not getting the ...
0
votes
1answer
32 views

If $s,t \in \Bbb N_{>0}$ are co-prime of distinct parities, then $\gcd(s^2-t^2, 2st, s^2+t^2)=1$

Suppose that $s>t$ where $s,t$ are positive integers of distinct parities. I want to show that if $s,t$ are co-prime of distinct parities, then $\gcd(s^2-t^2, 2st, s^2+t^2)=1$ Thoughts: Suppose ...
0
votes
0answers
43 views

The algebraic properties of a sequence

Take the sequence $S$ to be $4, 3, 8, 5, 12, 7, 16, 9, 20, 11, 24, 13,...$. Clearly the odd indices of the sequence are elements of $4\mathbb{N}^+$, so the odd indices of $S$ form a group without ...
0
votes
0answers
20 views

Solutions to cubic and higher degree functions

If $u = ax^2+a_2x+a_3$ is a quadratic polynomial then there exists a solution to $w=v^2$ where $w=cu+c_2$ and $v = bx+b_2$, which can be easily shown to be true. For instance when $u=x^2+x+1$, $w=4u-...
0
votes
0answers
12 views

Solving a non linear diophantine equation $px+y^{p-1}=2017$ [duplicate]

I had been tasked in an exam to solve this equation: $px+y^{p-1}=2017$ where $p$ is a positive prime number, and $x$ and $y$ are natural numbers. I was able to prove that if $p≥5$ then $p=7$, so now I ...
0
votes
1answer
28 views

Arithmetic of integer (based on mathematical induction)

If $m,n,p,q$ are non-negative integers, prove that $\sum_{m=0}^{q}(n-m)\frac{(p+m)!}{m!}=\frac{(p+q+1)!}{q!}\left (\frac{n}{p+1}-\frac{q}{p+2}\right )$ I tried for this but wasn't able to come up with ...
0
votes
2answers
32 views

Prove the modulo 12 pattern of $400*k^2 + 100k + 3$

Consider the formula $$400*k^2 + 100k + 3$$ where k are whole positive integers. The outcome of the modulo 12 values of x respectively seems to be: 11, 3, 3, 11, 3, 3 etc. This question comes up ...
1
vote
1answer
34 views

Proof for range of average

We can prove that average of two numbers $a,b$ where $a<b$ will be between $a$ and $b$ as follows $a < b$ $a + a < a + b$a < $\dfrac{a + b}{2 }$ $a < b$ $a + b < b + b$ $\...
0
votes
1answer
30 views

Arithmetic of integers (based on mathematical induction)

If $$f(n) = (3+\sqrt{5})^n + (3-\sqrt{5})^n$$ show that $f(n)$ is an integer and that $$f(n+1)= 6f(n) - 4f(n-1).$$ Deduce that the next integer greater than $(3+\sqrt{5})^n$ is divisible by $2^n.$ I ...
1
vote
4answers
65 views

Prove that $1^n+2^n+…+(n-1)^n$ is divisible by $n$ if $n$ is odd?

I've tried this with a few examples, but how would I show that it's true for EVERY odd number $n$? And why wouldn't it work for even number $n$?
1
vote
2answers
39 views

What is the largest prime factor of $\tau (20!)$

What is the largest prime factor of $\tau (20!)$ (where $\tau (n)$ is the number of divisors of $n$). This question arises in a chapter of my number theory notes where the author shows that $v_{p}(n) ...
0
votes
2answers
42 views

Why the last digit of $a^n$ is equal to the last digit of $a$ raised to power of $n$?

$17^3 = 4913$, and $7^3 = 343$, they share the same last digit. $15^4 = 50625$, and $5^4 = 625$. Also the same last digit, the question is why do they share the same last digit?
0
votes
1answer
31 views

$2(n-1)! \equiv -1 \mod n+2 \iff n+2$ is a prime

Problem: Show that $2(n-1)! \equiv -1 \mod n+2 \iff n+2$ is a prime. I know that Wilson's theorem states that $(n-1)! \equiv -1 \mod p $ for $p$ a prime, so that is the important thing to know with ...
2
votes
2answers
72 views

Counting the number of integers with their least prime factor greater than $x$ between $ax$ and $ax+x$

Let: $x \ge 2, a \ge 1$ be integers. $x\#$ be the primorial for $x$ $\mu(i)$ be the möbius function. $\text{lpf}(x)$ be the least prime factor of $x$. $p_k$ be the $k$th prime which is the highest ...
1
vote
0answers
45 views

Prove by induction that the product n(n+1)(n+2)…(n+r-1) of any consecutive r numbers is divisible by r! [duplicate]

I tried it by showing that true for r=0 and then assuming it to be true for r=k and trying to show it true for r=k+1. But I was not able to do that efficiently. So, please help me get a way out of it.....
0
votes
1answer
63 views

Why is $x = 25n + 9$ in the equation: $3=(3388997632 x^{23}) \text{ mod } 25$?

Apparently the general solution of this: $3=(3388997632\cdot x^{23}) \text{ mod }25$ is $x = 25n + 9$, where $n$ is any natural number, it seems? I get how there is connection with $25$ as modulo, ...
5
votes
3answers
114 views

Proof verification: Prove $\sqrt{n}$ is irrational.

Problem Let $n$ be a positive integer and not a perfect square. Prove $\sqrt{n}$ is irrational. Proof Consider proving by contradiction. If $\sqrt{n}$ is rational, then there exist two coprime ...
0
votes
4answers
45 views

I am looking for a proof of a certain set being divisible by 7

I am looking for a proof of this statement: $$7\mid{3^{6k+2}-{2^{6k+1}}}$$ By trial and error I can see that it holds but I cant figure out anyway to prove it or cant seem to be able understand why. ...
-2
votes
1answer
25 views

Application of Euclidean Algorithm [on hold]

Suppose x belongs to $\{{0,1,2,...,n-1}\}$. Also, y belongs to ${\{0,1,2,...,n-1}\}$. Use the Euclidean Algorithm to find a $x$ and a $y$ such that $x*y$ mod $n$ leaves a remainder of 1. That is, $(x*...
0
votes
1answer
24 views

Finding such that $xyz \equiv k \pmod{n}$, where $k, n$ are known?

What is an efficient way to choose three numbers $x, y, z$ such that $xyz \equiv k \pmod{n}$, where $k, n$ are given? I was thinking about choosing $x$ and $y$ randomly and then computing an ...
0
votes
2answers
30 views

A 3 digit number abc, $N=b(10c+b)$ where $b$ and $(10c+b)$ are primes.

A three-digit number $N$ has first digit $a$ (not equal $0$), second digit $b$ and third digit $c$. $N=b(10c+b)$ where $b$ and $(10c+b)$ are primes. Find $N$. $N = 100a+10b+c$ , then $100a+10b+c = ...
1
vote
2answers
53 views

Questions on Dirichlet's approximation theorem

In Wikipedia, the entry Dirichlet's approximation theorem states as follows: In number theory, Dirichlet's theorem on Diophantine approximation, also called Dirichlet's approximation theorem, ...
2
votes
1answer
70 views

Divisibility of $x^2+y^2$ by prime $p$

I've read the following fact on my number theory textbook, there's no proof on the book of such result, I tried working it out on my own but I'm kinda lost, the lemma is the following: Given two ...
-4
votes
0answers
24 views

Floor function linear addition [duplicate]

Find the number of real solutions of $\lfloor\frac12x\rfloor + \lfloor\frac23x\rfloor = x$
1
vote
0answers
45 views

Lipschitz primes

A Lipschitz integer is a Quaternion with integer coefficients. The norm is defined as $N(a+ib+jc+kd)=a^2+b^2+c^2+d^2$ which is a multiplicative function $N:\mathbb H\to\mathbb R$, $N(\alpha\beta)=N(\...
1
vote
1answer
28 views

Transpose of rational matrix is also rational

Rational numbers can be defined as those numbers $a \in \mathbb{R}$ for which there exists an integer $v \in \mathbb{Z}$ such that $av \in \mathbb{Z}$. Let us consider the following higher-dimensional ...