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

learn more… | top users | synonyms

4
votes
3answers
80 views

Can Number Theory be visualized?

So I was thinking about a hard euclidean geometry problem, when it hit me just how much more difficult it would become without the aid of a diagram. This got me thinking: Wouldn't it be great if we ...
1
vote
0answers
1 views

Sequence of non-collinear integer points.

This is a question from a British Olympiad, I've completed the first 3 but this one had me rather stumped. Given two points $P$ and $Q$ with integer coordinates, we say that $P$ sees $Q$ if the ...
3
votes
1answer
44 views

Pythagorean triples.

We are given $$ a^2 + p^2 = b^2 $$ where $a,b\in\mathbb{Z}$ and $p$ is prime. We are to show that $$2(a+p+1)$$ is a perfect square. Is there any elegant ways to go about this problem? Struggling to ...
0
votes
2answers
21 views

Determine the integers $a$ such that the congruence $x^4 \equiv a \pmod p$ has a solution for $p = 7, 11, 13$

Determine the integers $a$ such that the congruence $x^4 \equiv a \pmod p$ has a solution for $p = 7, 11, 13$ This looks similar to previous problem but kinda tricky. I'm not sure where to ...
4
votes
1answer
136 views

Does every record of the arithmetic derivative of natural numbers occur at a practical number?

Consider the arithmetic derivative of natural numbers, as defined here. By this definition, for every integer $n>1$, with canonical prime factorization ...
1
vote
2answers
26 views

Determine the integers $a$ such that the congruence $ax^4 \equiv b \pmod{13}$ has a solution for $b = 2, 5, 6$

Determine the integers $a$ such that the congruence $ax^4 \equiv b \pmod{13}$ has a solution for $b = 2, 5, 6$ I think the problem wants $a$'s that work for all $b=2,5,6$. Can I please have a ...
2
votes
2answers
44 views

Product of Divisors of some $n$ proof

The function $d(n)$ gives the number of positive divisors of $n$, including n itself. So for example, $d(25) = 3$, because $25$ has three divisors: $1$, $5$, and $25$. So how do I prove that the ...
7
votes
5answers
1k views

Express Integer as Sum of Four Squares

This is kind of a follow-up to the question I posted here about expressing integers as the sum of two squares. Is there a similar general method for expressing integers as the sum of four squares? I ...
1
vote
0answers
51 views

How to find integer solutions for $ax^2 + bx + c$

I am working on Integer factorization problem and I came to this: $$a = \frac{1-2b+\sqrt{4b^2 + 4b + 8c + 1}}{4}$$ c is the number that I want to factor $2a -1$, $a+b$ are factors of $c$ How to ...
0
votes
1answer
28 views

$d(n)$ is odd iff $n = k^2$ [duplicate]

The function $d(n)$ gives the number of positive divisors of $n$, including n itself. For example, $d(25) = 3$, because $25$ has three divisors: $1$, $5$, and $25$. Prove that $d(n)$ is odd if and ...
5
votes
0answers
20 views

A number $n$ which is the sum of all numbers $k$ with $\sigma(k)=n$?

For a positive integer $n$, let us define a set $$A_n = \{ k\in\mathbb{N} \mid \sigma(k) = n \}$$ where $\sigma$ is the divisor-sum function (a well-known multiplicative number-theoretic function). ...
1
vote
0answers
9 views

A bound on number of elements less than $n$ of a $B_2[g]$ sequence

Let $S \subset \mathbb{N}$. We say $S$ is of type $B_2(g)$ if the number of representation of the form $n = s_1 + s_2 \ (s_1 \leq s_2)$ is bounded by $g$ for every $n \in \mathbb{N}$. Let $S(n)$ be ...
3
votes
2answers
66 views

Starting with $13^{2013}$ can we get $2013^{13}$ by the following process.

This is the problem that I found in a question paper. The problem is: A positive integer is written on the board. We repeatedly erase its unit digit and add 4 times that digit to what remains. ...
0
votes
0answers
13 views

Number of solutions of the congruence, $x-y \equiv z \pmod{n}$, where $x,y$ in a set contain less than $n$ and relatively prime to $n$?

I known number of solution of the congruence, $x+y \equiv z \pmod{n}$,$x,y\in U_{n}$ is $N(z)=n\prod_{ p\backslash n}\left(1-\frac{\varepsilon(p)}{p}\right)$, ...
4
votes
0answers
115 views

Find all the solutions of $x^2+7=2^n$. [duplicate]

Checking for some small natural numbers $n$, I found out that $2^n-7$ is a perfect square for $n=3,4,5,7,15$. How can we find all of the numbers $n$ for which $2^n-7$ is a perfect square? What I ...
11
votes
2answers
123 views

When is $2^n -7$ a perfect square?

This came up while solving another ENT problem. I want to ask when is: $$2^n -7 \text{ where } n\geq 3$$ a perfect square? Specifically, I also wanted to know what would be the solutions when $n$ is ...
4
votes
0answers
50 views

Rationality and triangles

Consider a triangle with angles $\alpha, 5\alpha, 180-6\alpha$. What is the minimum perimeter of that triangle, if it has integer sides and $5\alpha<90$?. Let's call tha sides that face each ...
4
votes
2answers
375 views

$\mathrm{lcm}(1, 2, 3, \ldots, n)$?

I want to find $\mathrm{lcm}(1, 2, 3, \ldots, n)$ where $2 \le n \le 10^8$ . I'm trying to find a formula . Please Help .
6
votes
4answers
849 views

Prove by induction: $2^n + 3^n -5^n$ is divisible by $3$

Let $P(n) = 2^n + 3^n - 5^n $. I want to prove that $P(n)$ is divisible by $3$ for all integers $n\geq 1$. The basis step for this proof is easy enough: $P(1)$ is divisible by $3$. For the ...
3
votes
1answer
28 views

Show that $\mathrm{gcd}(x+4,x-4)$ divides $8$ for all integers $x$.

I want to prove that $\mathrm{gcd}(x-4,x+4)$ divides $8$ for all $x\in \mathbb{Z}$ Since they are both polynomials of degree $1$, it suggests that the $\mathrm{gcd}$ is a constant. Using Euclidean ...
1
vote
0answers
25 views

elementary number theory exercise 2.22 [on hold]

let $X_n$=$p_1$$p_2$...$p_n$ and $a_k$=$1+kX_n$ where $p_1$up to $p_n$ are prime numbers and $k$ ranges from $1$ to $n-1$ , show that if $i$ is not equal to $j$ then gcd of $a_i$ and $a_j$ is equal to ...
10
votes
2answers
157 views

If $3^x$ and $5^x$ are both integers, is $x$ an integer?

Does the following statement hold? $$x\in \mathbb{R}^+ \text{and} \ 3^x, 5^x \in \mathbb{Z} \implies x \in \mathbb{Z}$$ In words: If $x>0$ is a real number, and $3^x$ and $5^x$ are ...
0
votes
1answer
41 views

If $2^{k} + 1$ is prime, prove that $k$ has no other prime divisors than $2$. [duplicate]

I am trying to prove this by contradiction: Assume $2^{k} + 1$ is prime. By definition of odd number $2^{k} + 1$ is odd because $2^{k} + 1 = 2\cdot 2^{k-1} + 1$ Then $2^{k} + 1 \pmod{2} \equiv 1 ...
0
votes
2answers
100 views

In Wilson's Theorem Why can we always split integers into mutually inverse pairs?

I mean for example $p=13$ $1*12\equiv-1 \pmod{13}$ then inverse pairs $2*7\equiv1\pmod{13}$ $3*9\equiv1\pmod{13}$ $4*10\equiv1\pmod{13}$ $5*8\equiv1\pmod{13}$ $6*11\equiv1\pmod{13}$
7
votes
2answers
165 views

$n\mid \phi(a^{n}-1)$ for any $a>n$?

I saw the proof which goes as follows: $a^{n} \equiv 1 \pmod{a^{n}-1} $, and $n$ is the smallest power of a such that this is true. We also know that by Euler's Identity $a^{\phi(a^{n}-1)}\equiv ...
7
votes
4answers
81 views

For what integers $n$ does $\phi(2n)=\phi(3n)$?

For what integers $n$ does $\phi(2n)=\phi(3n)$? I know that $\phi(n) = \phi(P_1^{a1})\cdots\phi(P_k^{ak}) = (P_1^{a1}-P_1^{a1-1})\cdots(P_k^{ak}-P_k^{ak-1})$ but I'm not really sure how to apply it ...
2
votes
1answer
87 views

The number of summands $\phi(n)$

If $n$ is a positive integer such that the sum of all positive integers $a$ satisfying $1\leq a\leq n$ and $\gcd(a,n)=1$ is equal to $240n$ then the number of summands namely $\phi(n)$ is 120 124 ...
2
votes
3answers
87 views

If $a$ and $b$ are odd integers, then $\sqrt{a^2+b^2}$ is irrational

If $a,b\in\mathbb{N}$ are odd then demonstrate: $$ {\sqrt{a^2 + b^2}} \not\in \mathbb{Q}$$ I try to guess that $$ {\sqrt{a^2 + b^2}} \in\mathbb{Q}.$$ Then i write $$ {\sqrt{a^2 + b^2}= m/n}.$$ ...
3
votes
4answers
356 views

A consequence of Wilson's Theorem

By Wilson's Theorem we know that $$(p-1)! \equiv -1 \mod p.$$ A consequence of this is apparently $$(p-(k+1))!k! \equiv (-1)^{k+1} \mod p$$ where $0 \leq k \leq p-1$. I was told to think of it like ...
4
votes
3answers
193 views

If $x\in\mathbb R$, solve $4x^2-40\lfloor x\rfloor+51=0$.

If $x\in\mathbb R$, solve $$4x^2-40\lfloor x\rfloor+51=0$$ where $\lfloor x\rfloor$ denotes the integer part of the number. $\lfloor x\rfloor\le x$ and $\lfloor x\rfloor=x-\{x\}$, where $\{x\}$ ...
0
votes
1answer
11 views

“Multivariable” version of this lemma about showing analytically that a number is irrational.

Lemma: let $\alpha \in \mathbb{R}^+$ and $p_1,p_2,\dots, q_1, q_2, \ldots \in \mathbb{N}$ such that $\left|\alpha q_n - p_n \right| \neq 0$ for all $n \in \mathbb{N}$ and $$ \lim_{n \rightarrow ...
0
votes
3answers
31 views

Proving if $p|ab$ then $p|a\vee p|b$, then $p$ is prime

Let $1\neq p\in \mathbb N$ such that $\forall a,b \in \mathbb N$ if $p|ab$ then $p|a\vee p|b$. Prove that $p$ is prime. My attempt, proof by contradiction: Suppose $p$ isn't prime, then ...
-2
votes
1answer
89 views

Prove $x^{p^2-1}\equiv1\pmod{p^2}$ has exactly $p-1$ solutions for prime $p$ [on hold]

Let $m=p^2$ where $p$ is a prime number. Show that the congruence $x^{m-1}\equiv 1\pmod{m}$ has precisely $p-1$ solutions. Let $m = pq$ where $p$ and $q$ are distinct prime numbers. Show that then ...
23
votes
6answers
11k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
1
vote
1answer
31 views

Showing that every positive integer can be represented in this form

How can we prove that for every pair $N \in \mathbb{N}$, and natural number $\beta\in [2, \infty)$ there exists a unique set of integers $x_i \in [0, \beta -1]$, $k\in [0,\infty)$ such that: $$N = ...
-3
votes
3answers
60 views

A number that leaves a remainder of $1$ when divided by $2,3,4,5,6,7$ [on hold]

What is a number that when divided by $2,3,4,5,6,7$ leaves a remainder of $1$? I have tried some sample numbers, but I am interested in a general solution. Any ideas?
2
votes
1answer
52 views

Existence of solution to Congruence relation $(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$

I'm taking the final exam in "Number Theory" tomorrow and stuck with: Prove that $\,\,\forall p\in\mathbb{Z}_p\,$ the congruence relation: $$(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$$ has a ...
0
votes
1answer
10 views

A limited composition of two unlimited functions on natural numbers?

Can someone give an example of two functions $f,g:\Bbb N\to \Bbb N$ such that $|\operatorname{Im}f|,|\operatorname{Im}\,g|\notin\Bbb N$, but such that $|\operatorname{Im}\,g\circ f|\in\Bbb N$?
0
votes
1answer
16 views

Finding a module for the series $2^{i}$ from 0 to 219

How can I compute this: $\{ \sum 2^{i}$ for $i \in [0, 219] \} \pmod{13}$ I tried to manipulate the series by using the root principle to find the number of elements divisible by every prime $\leq ...
2
votes
2answers
50 views

Determine if $-42$ is a quadratic residue of $\pmod{61}$

This is what I have so far: Using Legendre symbol, we have $(\frac{-42}{61})\equiv(\frac{19}{61}).$ Since $\mathrm{gcd}(19,61)=1,$ $(\frac{19}{61})\equiv1.$ Is this correct?
2
votes
1answer
163 views

Solutions of Diophantine equations in Natural numbers

The one of solution of $x^4 - 2y^2 = -1$ is $x = 1$ and $y = 1$. However, the solution $(1, 1)$ of $x^4 - 2y^2 = 1$ is failed. We know $x = 1$ and $y = 1$ is small integers and we can check by trail ...
0
votes
1answer
79 views

Diophantine equation exercise [duplicate]

Prove that the diophantine equation $x^4-2(y^2)=1$ has only 2 solutions. Any hint on how to start and what to do .. I do not have a lot of experience on non linear diophantine equations and do not ...
0
votes
2answers
62 views

GCD and LCM Problem

Let $x$ and $y$ be positive integers, $x < y$, and $x + y = 667$. Find all pairs $(x,y)$ if $\text{lcm}\,(x,y)/\gcd\,(x,y) = 120$. This problem was from my number theory homework, and I don't get ...
12
votes
1answer
142 views

Twelve Distinct Positive Integers

Let S be a set of twelve distinct positive integers such that for distinct a, b, c, and d in S, a + b ≠ c + d. Show that the largest element in S is greater than 56. I found some math competition ...
0
votes
2answers
76 views

What is the upper bound for $\frac1n$ where $n$ is a prime? [on hold]

What is the upper bound for $\frac1n$ where $n$ is a prime? Apparently this has something to do with repeating decimals and the period of a decimal.
3
votes
2answers
40 views

Suggestion to a book with lots of number theory problems

What I am looking for is a book that contains "infinitely many problems", starts from the easiest to high level(that can be found in national and even international olympiads). Are there such books, ...
5
votes
2answers
144 views

If $\frac{a+1}{b}+\frac{b}{a}$ is an integer then it is $3$.

If $\frac{a+1}{b}+\frac{b}{a}$ is an integer for positive integers $a,b$ then prove that this integer is $3$. I reduced the to prove that if $\frac{c^2+d^2+1}{cd}$ is an integer then it is $3$ where ...
2
votes
2answers
61 views

Find all primes $p$ with some given conditions.

Find all primes $p$ such that $p^2-p+1$ is a perfect cube. I found out that p is of the form $18n+1$ and $p=19$ is a solution but I am not getting anything further. $p^2-p-(m^3-1)=0$ ...
0
votes
5answers
73 views

Prove that if you divide $10^n$ by $9$ then the remainder is $1$

$n=1$ Then $\frac{10^1}{9} = \frac{10}{9}$ remainder = $1$. For $n\geq2$, how does you do this? I want to prove that last digit is always zero, of $10$ raised to power. How do I do that please by ...
2
votes
4answers
80 views

How do I prove that if $p$ is prime then $p$ divides $2^{p}-2$?

I know that if $p$ divides $2^{p}-2$ can be written as $2^p - 2 \equiv 0 \bmod p$, but then I get stuck. Im not sure how to take an approach on this.