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

learn more… | top users | synonyms

0
votes
1answer
20 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
72 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
28 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 ...
3
votes
0answers
12 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
41 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
192 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 ...
10
votes
3answers
419 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
32 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
22 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
55 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 ...
3
votes
1answer
61 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 ...
3
votes
2answers
69 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
26 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
35 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
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 ...
11
votes
2answers
130 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
16 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
61 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
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 ...
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
17 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
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 = ...
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.
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
23 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
50 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
27 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
61 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
29 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
38 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
82 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 ...
1
vote
1answer
26 views

If $x$ is a square modulo two primes, then it is a square modulo their product

$a, b$ be integers, $p, q$ primes. If $x \equiv a^2 $ (mod $p$) and $x \equiv b^2$ (mod $q$), then $x \equiv c^2$ (mod $pq$) for some interger $c$. I attempted to use Chinese Remainer Theorem, ...
0
votes
0answers
16 views

Positive solutions of a diophantine equation

When looking at the positive solutions on $x,y \in \mathbb{Z}$ of the equation: $$ax+by=c$$ with $a,b \in \mathbb{N}$ Granted that $g = gcd(a,b)$ divides c, we found that the inequality: ...
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
3answers
42 views

Is this mod equality true?

I wish I could add my thoughts here, but I've really couldn't figure out anything interesting myself. $(a \mod C + b \mod C)\mod C = (a+b) \mod C$
4
votes
1answer
58 views

Prove that there are no positive integers $a, b$ and $n >1$ such that $a^n – b^n$ divides $ a^n + b^n$.

Prove that there are no positive integers $a$ , $b$ and $n>1$ such that $a^{n}–b^{n}$ divides $a^{n}+b^{n}$. Can someone provide me a proof of this and explain it to me please.
1
vote
1answer
20 views

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$ I know $r^{p-1}\equiv 1 \pmod {p} \implies r^{(p-1)/2}\equiv -1 \pmod{p}$ But some how I feel the ...
0
votes
2answers
20 views

Representing number $X$ in base $r$

In general, let $X = (X_{n−1}X_{n−2}...X_0)_r$ be an n-digit number in base r. Give an algorithm or explain in English how to represent $X$ in base $r^2$. I ...
0
votes
1answer
53 views

Natural numbers not expressible as $x+s(x)$ nor $x+s(x)+l(x)$

For positive integers $x$, let $s(x)$ denote the sum of the digits of $x$, and $l(x)$ denote the number of digits of $x$. It seems that other than $n=1$ and $n=20$, there always exist $x$ such that ...