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
vote
0answers
34 views

A riddle on positive integers - Ann and Bob

There are two agents: Ann and Bob. Suppose: I tell Ann an integer finite positive number n (n>0) I tell Bob an integer finite positive number m (m>0) I tell both Ann and Bob that either n=m+1 or ...
1
vote
1answer
33 views

Let $d(n)$ be the number of positive divisors of $n$. Find all $n$ such that $\frac{n}{d(n)}$ is prime.

Let $d(n)$ be the number of positive divisors of $n$. Find all $n$ such that $\frac{n}{d(n)}=p$, a prime. If $n=\prod_{1\leq i \leq k} p_i^{r_i}$, then \begin{eqnarray*} n&=&p_1\cdot d(n)=...
4
votes
0answers
55 views

Unique representation of numbers of the form $p^n - p$

Consider numbers of the form $p^n - p$ where $p>2$ is a prime and $n>1 \in \mathbb{Z}$. How many of these have a unique representation? $2184$ has at least $2, 3^7-3, 13^3-13$, do any other ...
0
votes
4answers
48 views

Divisibility of a large number

Let $N$ be a large number of 258 digits consisting all 1's except two digits at 145th and 146th digits. If $N$ is divisible by 17 then what is the two missing numbers?
0
votes
1answer
23 views

Digit problem enumeration

We have four digit number $abcd$. How many are there such numbers are such that $bcd$ = 2*$abc$? My attempt: I wrote down some examples, but solution is not so obvious to me.
0
votes
1answer
26 views

Prime number and fraction problem

$p$ is a prime number and $m$ is a whole number, how many pairs of $(p,m)$ exist such that $\frac{m^3-pm+1}{m^2 + pm + 2}$ is a prime number? My attempt: Obviously the denominator should be able to ...
2
votes
1answer
38 views

Find how many solutions the congruence $x^2\equiv -1 \mod 61$ has

I tried it has two solutions $\pm 30!~mod~61$ but I need explicitely what are those? I have seen similar problems in this site but I didn't get the solution completely.
0
votes
2answers
44 views

Of 100 questions about numerals and numerical bases, these I could not solve. I need help! [on hold]

1) What change has the number 6783, when inserting a zero between the numbers 7 and 8?
1
vote
1answer
41 views

How to check $x^2+y^2+z^2=7 w^2$ admits no no-trivial integral solution?

This is a statement made in Lam's Introduction to Quadratic Forms Chpt 1, Sec 2. "7 is known not in $D(f)$ in elementary number theory" where $D(f)=\{(x,y,z)\in Q^3, x^2+y^2+z^2=7\}$ and $Q$ is ...
0
votes
4answers
53 views

$b^{n-1} \equiv 1$ $mod$ $n$ implies gcd($b$,$n$) = $1$

I want to prove that if $b^{n-1} \equiv 1 \pmod n$ then $\mathrm{gcd}(b,n) = 1$ as long as $n > 1$. I believe this to be true and think its connected to Fermat's Little Theorem somehow, but I can'...
0
votes
1answer
21 views

Chinese remainder theorem and quadratic congruences

By Chinese remainder theorem there is a solution to $x \equiv a_{1} \pmod{ p_{1}}, \ ..., \ x \equiv a_{k} \pmod{ p_{k}}$ if $p_{1}, \ ..., \ p_{k}$ are pairwise coprime and $a_{1}, \ ..., \ a_{k}$ ...
-6
votes
0answers
52 views

2 = 0/0 what's wrong with this equality? [on hold]

$2 = \frac{2}{1} = \frac{20}{10} = \frac{10+10}{10} = \frac{10+10}{10}\cdot\frac{10-10}{10-10} = \frac{10^2-10^2}{100-100} =\frac{100-100}{100-100} =\frac{0}{0}$ Is this even possible?
2
votes
0answers
37 views

Is there a formal term for the algebraic structure equivalent to Thurston's hemigroup without identity? [duplicate]

This question is not a duplicated of https://math.stackexchange.com/a/3183330/342834 . It is a follow-on, asking about the distinction between the subject of that post, and the subject of this post. ...
1
vote
1answer
41 views

Prove that if $a$ and $b$ are coprime then so are $a^n$ and $b^m$

I have to prove that if a and b are relatively prime then so are $a^n$ and $b^m$ by contrapositive I'm asking for help please because i really don't know how to proceed and this assignment is due ...
1
vote
3answers
53 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
50 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] \...
-5
votes
0answers
36 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
450 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
38 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 ...
2
votes
1answer
41 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
73 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
2answers
73 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$
1
vote
2answers
44 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
34 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
46 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
43 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
2answers
81 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}$. ${\bf Questions:}$ Are there finitely many solutions? If no,...
4
votes
1answer
149 views
+100

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+(...
11
votes
2answers
192 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
48 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 ...
-1
votes
2answers
58 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
60 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
44 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 ...
5
votes
0answers
92 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
35 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
32 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
67 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
40 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
43 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 ...