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

learn more… | top users | synonyms

1
vote
2answers
26 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
14 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
18 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
9 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 ...
0
votes
1answer
39 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
44 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
43 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
15 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
17 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
74 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
41 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
21 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
46 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
39 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
25 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
38 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
28 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
34 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
78 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
25 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
44 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
38 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
57 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
19 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
14 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
39 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 ...
0
votes
1answer
21 views

Number Theory: Finding specific new square-triangular numbers given that (m, n) satisfied n^2=m(m+1)/2

Ok, so I've been making my way through my beginning number theory homework, and I've come to this problem. In all honesty, I don't even know where to start, so I would greatly appreciate any advice ...
1
vote
1answer
34 views

If $p$ is a prime and $p$ divides $a^3$ then $p$ divides $a$ [on hold]

I have to either give a proof or provide a counterexample for this question. $a, b$ are non-zero intergers. If $p$ is a prime and $p|a^3$ then $p|a$ I think this is true but do not know how to go ...
0
votes
1answer
33 views

Prove elements of a set are not uniquely representable.

Let $E = \{2k: k \in \Bbb{N}\}$, and let $M = \{m = (2r)(4a + 2) : r, a \in \Bbb{N}\}$. Prove that some elements in $E$ are not uniquely representable as products of elements of $M$, e.g. ...
0
votes
1answer
54 views

Solve $9x^8\equiv 8\pmod{17}$

$$9x^8\equiv 8\pmod{17}$$ Is there a way to solve this with out testing all integers $x$ between $1$ and $17$ ?
4
votes
0answers
75 views

Improvement IMO 1988 $f(f(n))=n+1987$

The following problem was given at IMO 1987. Prove that there is no function f from the set of non-negative integers into itself such that $f(f(n)) = n + 1987$ for every $n$. So I tried to ...
3
votes
2answers
32 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, ...
1
vote
4answers
36 views

Three different examples of three consecutive triangular numbers whose sum is a perfect square for n > or equal to 20

Three different examples of three consecutive triangular numbers whose sum is a perfect square for n > or equal to 20. (In other words their sum must be greater than or equal to 400 and must be a ...
1
vote
2answers
67 views

The equation $x^4+y^4=z^2$ has no integer solution

The equation $$x^4+y^4=z^2$$ has no integer solution for $(x, y, z), x \cdot y \neq 0 , z >0$. We suppose that there is a solution $(x, y, z)$. We consider the set $$M=\{z \in \mathbb{N} | ...
3
votes
2answers
32 views

Is there are integer solutions for this equation: $ 65x-4y= 129$ [on hold]

My question is: Is there are integer solutions for this equation: $$ 65x-4y= 129$$
4
votes
0answers
44 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 ...
1
vote
1answer
25 views

A functional equation over integers

I was working in a problem in number theory and I blocked over the problem : Given functions $f:\mathbb{Z}\rightarrow \mathbb{Z}$, $g:\mathbb{Z^2}\rightarrow \mathbb{Z}$ and ...
0
votes
1answer
36 views

If $p^q - 1$ is a prime, then $p=2$ and $q$ is a prime [duplicate]

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $p$ and $q$ are positive integers ($\mathbb{Z}^+$) such that $q \gt 1$ and $(p^q - 1)$ is ...
0
votes
1answer
18 views

How to use totient function here?

I have asked this before, but I had no idea how to use Totient, now I do here is the questions: How many positive integers $< 2013$ cannot be divided by $2, 3, 5$ ?? An advice given was find ...
0
votes
1answer
8 views

Primitive roots and 'equivalent exponents'.

If M is a primitive root mod p and M = $\ N^T$ mod p , then the order of N mod p is also (p-1) is this true?
1
vote
0answers
23 views

For what positive integer values $b,d$ does $(b^2-d)\mid(b^2-1)?$ hold?

I am curious about the answer to the following questions: And hope that you can help me For what positive integer values $b, d$ does $$(b^2-d)|(b^2-1)?$$ hold? Is it correct that the only ...
2
votes
2answers
52 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$ ...
1
vote
4answers
57 views

The divisibility of $a^p-1$ by $a-1$ and by $(a-1)^2$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : Let a $\geq$ 2 and p be any positive integers , then prove that : $(a-1) \mid(a^p - ...
3
votes
2answers
150 views

Prove that any power of a prime is not a perfect number [on hold]

How do I prove: Let $p$ be a prime, and $n$ be a positive integer. Then $p^n$ is not a perfect number. One example is when $p = 2$ and $n = 3$, the question is to show $8$ is not a perfect ...
3
votes
2answers
53 views

Find the $n$ for which $σ(n) = 15$ [on hold]

$σ(n)$ is the sum of the divisors of $n$, including $n$ itself. Find the $n$ for which $σ(n) = 15$, and also how do I prove that $n$ is unique.
2
votes
1answer
31 views

Convert the following decimal number into 32-bit IEEE floating-point form.

I am given a negative decimal -1234.875. I understand the normal process of solving a question like this, except I am uncertain about handling the negative. What I do is find the binary form of 1234 ...
1
vote
3answers
33 views

Proving by contradiction that if $a\in\mathbb Q,b\in \mathbb R\setminus \mathbb Q$ then $a+b\in \mathbb R \setminus \mathbb Q$

I'm trying to prove by contradiction that if $a\in\mathbb Q,b\in \mathbb R\setminus \mathbb Q$ then $a+b\in \mathbb R \setminus \mathbb Q$, I already proved it with contra position and a direct proof ...
7
votes
0answers
71 views

Olympiad-style question about functions satisfying condition $f(f(f(n))) = f(n+1) + 1$

QN: What functions (from non-negative integers to non-negative integers) satisfy the condition $$f(f(f(n))) = f(n+1) + 1$$ Comment: Evidently $f(n) = n+ 1$ is one solution. Equally evidently no ...