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

learn more… | top users | synonyms

3
votes
0answers
45 views

Olympic number theory problem: is this solution fine and sufficiently well written?

Determine all the positive integers $m$ such that both the ratios $$ \frac{2(5^m+5)}{3^m+1}, \frac{9^m+1}{5^m+5}$$ are integers. Attempt to a solution: If the ratios are both integers, than their ...
1
vote
2answers
33 views

Let $k \geq 2 \in \mathbb{N}$ Show that each of $k! +2, k! +3, … , k! +k$ is composite.

Let $k \geq 2 \in \mathbb{N}$ Show that each of the numbers $k! +2, k! +3, ... , k! +k$ is composite. So, firstly I'm not sure I fully understand the question. Surely let $k = 2$ then $2!+3 = 5$, ...
1
vote
2answers
47 views

There does not exist a polynomial $p(x)$ with integer coefficients which gives a prime number $\forall x\in \mathbb{Z}$ [duplicate]

There does not exist a polynomial $p(x)$ with integer coefficients which gives a prime number $\forall x\in \mathbb{Z}$ My attempt: I defined a polynomial as ...
2
votes
3answers
71 views

Prove that the equation $a^2+b^2=c^2+3$ has infinitely many integer solutions $(a,b,c)$.

Prove that the equation $a^2+b^2=c^2+3$ has infinitely many integer solutions $(a,b,c)$. My attempt: $(a+1)(a-1)+(b+1)(b-1)=c^2+1$ This form didn't help so I thought of $\mod 3$, but that didn't ...
1
vote
1answer
19 views

Show that in an integral right angled triangle, area is not perfect square.

Show that in an integral right angled triangle, area is not perfect square. I tried a few things, one of the being using the stereotype pythagoras form of the number, and tried drawing a few squares, ...
3
votes
1answer
34 views

Let $p$ be a prime. Show that ${n \choose p}-\bigl[\frac{n}{p}\bigr]$ is divisible by $p$, for all $n\in \mathbb{N}$ [duplicate]

Let $p$ be a prime. Show that $${n \choose p}-\bigg[\dfrac{n}{p}\bigg]$$ is divisible by $p$, for all $n\in \mathbb{N}$. I could not attempt this problem at all. Please help. Thank you. EDIT: Here ...
2
votes
1answer
20 views

Let $\{a_n\}$ be the sequence of positive integers defined by $a_n=20+n^2$.Set $d_n=\gcd(a_n,a_{n+1})$. Show that $d_n\mid 81$, also… [duplicate]

Let $\{a_n\}$ be a sequence of positive integers defined by $a_n=20+n^2$. Set $d_n=\gcd(a_n,a_{n+1})$. Show that $d_n\mid 81$ and also find all possible values of $d_n$. Show that each of those values ...
0
votes
0answers
14 views

numerical grouping using matlab / octave

I have several hundred numbers that I would like to group together based on octaves or increments of octaves. PS: An octave of 440hz is 220hz Example: ...
0
votes
4answers
44 views

Divisibility. $k= \frac{3^{77}-1}{2}$ [on hold]

How to prove that: $$ k= \frac{3^{77}-1}{2}$$ is not prime and $2$ doesn't divide $k$? And second: How to prove that $10$ doesn't divide: $321^{654} + 123^{456}$
0
votes
1answer
22 views

Show that $x^4 \equiv -1\pmod p $ is solvable $\iff $ $ p \equiv 1 \pmod 8$

Show that $x^4 \equiv -1 \pmod p $ is solvable $\iff $ $p \equiv 1 \pmod 8$ My attempt : $p$ must satisfy $(-1)^{(p-1)/d}\equiv 1 \pmod p$, where $d = \gcd(4,p-1)$ but I still don't see how this ...
3
votes
1answer
76 views

If $N=a^2+b^2=c^2+d^2$ then $N$ cannot be a prime number.

The problem says that if $N$ can be expressed in two ways as the sum of two squares then $N$ is not prime. Clearly the first idea is to try and express $N$ as a product of two expressions containing ...
2
votes
1answer
32 views

$S=\{0,1,2,…,q^2-1\}$, is there a way to figure out how many elements contained in $S$ can be written as the sum of $2$ squares?

I'm currently working on a proof, and have broken it down into a series of problems. I've had success with every part except one. My question is (and it may be really easy; it's getting late): 'Let ...
4
votes
0answers
13 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 ...
2
votes
3answers
56 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 ...
5
votes
1answer
205 views

If $a^2 + p^2 = b^2$ then $2(a+p+1)$ is a perfect square

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 ...
15
votes
3answers
703 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
2answers
28 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 ...
1
vote
1answer
33 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 ...
6
votes
0answers
26 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). ...
3
votes
1answer
62 views

Euler's function $\phi$: Values such that $\phi(n)=8$, $\phi(n)=14$

Let $\phi(n) $ be Euler's Totient Function Let us consider $$ |\{ n \in \mathbb{N} : \phi (n) = 8 \} | = 5, $$ and $$ |\{ n \in \mathbb{N} : \phi (n) = 14 \} | = 0. $$ How would I go about ...
4
votes
2answers
73 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. ...
1
vote
0answers
27 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 ...
4
votes
1answer
38 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 ...
0
votes
1answer
42 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 ...
11
votes
2answers
131 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 ...
0
votes
0answers
19 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)$, ...
0
votes
3answers
32 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
3answers
62 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?
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
18 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 ...
0
votes
5answers
75 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
2answers
47 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 ...
2
votes
2answers
19 views

Need Verification on a Modulus Proof

So basically I have to prove: n ≡ 1 (mod 4) if and only if n ≡ 1 (mod 8) or n ≡ 5 (mod 8). Is this a sufficient proof: $4 \times 2n + 1= 8 \times n + 1 \equiv 1 \pmod {8}$ where $n$ is an integer ...
1
vote
1answer
23 views

Primitive Roots Modulo $2^n$ for $n\geq3$

Question: (a) Prove that there is no primitive root modulo $2^n$ for any $n\geq3$, where $\bar{a}\in(\mathbb{Z}/2^n\mathbb{Z})^\ast$ is a primitive root modulo $2^n$ if the order of $\bar{a}$ is ...
0
votes
1answer
11 views

GCD of 1: Prove set is Complete Residue System Proof [on hold]

Suppose that $m$ and $n$ are integers with greatest common divisor $1$. Assume that both are greater than $1$. Prove that the set ${0 · n, 1 · n, 2 · n, . . . ,(m − 1) · n}$ is a complete residue ...
1
vote
1answer
47 views

Is the solution to this elementary number theory problem correct?

Problem: A natural number $n$ is called nice if the following properties hold: • The expression is made ​​up of 4 decimal digits; • the first and third digits of $n$ are equal; • the second and ...
-2
votes
2answers
47 views

What is $\sqrt{3}\pmod 2$?

Please explain your answer, thanks. My attempt: It is $\pm 1$ because $(\pm 1)^2\equiv 1\equiv 3\pmod 2$, so $\pm 1\equiv \sqrt{3}$ by taking square roots.
0
votes
2answers
48 views

How to find $\sqrt{3}\pmod 5$?

I was thinking about this but I couldn't solve it. I am trying to find $\sqrt{3}\pmod {10}$. I found that $\sqrt{3}\equiv \pm 1\pmod 2$ but I can't solve $\sqrt{3}\pmod 5$. Thanks
1
vote
3answers
18 views

Where am I going wrong in my linear Diophantine solution?

Let $-2x + -7y = 9$. We find integer solutions $x, y$. These solutions exist iff $\gcd(x, y) \mid 9$. So, $-7 = -2(4) + 1$ then $-2 = 1(-2)$ so the gcd is 1, and $1\mid9$. OK. In other words, ...
1
vote
1answer
32 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
4answers
82 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.
2
votes
1answer
46 views

Pythagorean Quadruples Problem

What are all the solutions to $$2^{2x}+2^{2y}+1=n^2 $$ I tried using the parametrization of Pythagorean Quadruples, but it did not work quite well. There are $2$ parametrizations: ...
1
vote
1answer
24 views

existence of solution to congruence $x^4 \equiv -4 \pmod p$

I stuck with the following question: For which $p$ (prime numbers) there is a solution for the following congruence: $x^4 \equiv -4 \pmod p$ I would greatly appreciate any help
1
vote
4answers
53 views

Does Bezout's lemma work both ways.

I know that if $a$ and $b$ have a highest common factor $h$ then you can write $h=ax+by$ for some $x,y \in \mathbb{Z}$ but how about if you can write $h=ax+by$ for some $x,y \in \mathbb{Z}$ then can ...
1
vote
2answers
42 views

If $X$ and $Y$ are coprime to $Z$, then so is their product $XY$

Given is $X$ is coprime to $Z$ and $Y$ is coprime to $Z$ prove $XY$ is coprime to $Z$. I know you can use Bezout's lemma to say $1=aX+bZ$ and $1=cY+dZ$ but I don't know how to actually do the proof. ...
0
votes
2answers
28 views

Splitting sum into two sums

Assuming that $f$ is a multiplicative arithmetic function. Let $n_1,n_2\in \mathbb{N}$ with $gcd(n_1,n_2)=1$. Consider the sum $$\large S=\sum_{a\mid n_1n_2}f(a).$$ Can I split the sum $S$ into two ...
0
votes
1answer
63 views

Definable real numbers

Reading this Wikipedia page I found this definition: A real number $a$ is first-order definable in the language of set theory, without parameters, if there is a formula $\phi$ in the language ...
1
vote
3answers
31 views

Difficult proof about coprime and factors of numbers!

I am attempting a proof but it is driving me insane as I cannot see what I should do. Given that $a$ is coprime to be $b$ and that $a|c$ and $b|c$ prove $ab|c$. I simply wrote down what I know and ...
2
votes
1answer
39 views

What is the point of big Oh notation when it is used for estimation?

I'm reading a book on number theory at the moment that assumes familiarity with big Oh notation...and while I think I do understand the notation I cannot understand the point of it. For instance let ...
4
votes
2answers
85 views

A puzzle about a sum and product of two numbers

The Gray Man wants to test The Hardy Boys. He says to them, "I've selected 2 positive integers, both bigger than one." He then proceeds to reveal their total and product to Frank and Joe ...