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

learn more… | top users | synonyms (1)

4
votes
1answer
28 views

Can two perfect squares average to a third perfect square?

My question is does there exist a triple of integers, $a<b<c$ such that $b^2 = \frac{a^2+c^2}{2}$ I suspect that the answer to this is no but I have not been able to prove it yet. I realize ...
2
votes
1answer
35 views

Non-square modulo 9

I'm a little confused by a (seemingly) elementary claim made in a paper: Let $n$ be a non-square in $\mathbb{F}_9$. Then $n^4 \equiv -1 \mod 9$. The squares modulo $9$ are $0 , 1 ,4 , 7$, and if I'm ...
5
votes
1answer
92 views

Prove by combinatorial method that $ \frac{(2m)! \cdot (2n)!}{(m)! \cdot (n)! \cdot (m+n)!} $ is an integer [duplicate]

Prove that $$ \dfrac{(2m)! \cdot (2n)!}{(m)! \cdot (n)! \cdot (m+n)!} $$ is a positive integer, where $(m,n) \in \mathbb{Z^{+}}$ I have already solved it using Legendre's Formula ...
2
votes
1answer
21 views

for any positive integer $a,b,n$,and $(a,b)=1$,Is $\frac{1}{a+b}+\frac{1}{a+2b}+\cdots+\frac{1}{a+nb}$ non integer,and How to prove that?

It's easy to prove that both $\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ and $\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2n+1}$ are nonintegers by multiply $2^k$and $3^k$, and how about the ...
-1
votes
2answers
55 views

Prove $10^{n-1}\le a \lt 10^n$

$$ \forall a \in \mathbb{N}: \quad a = a_{n-1}\times10^{n-1} + a_{n-2}\times10^{n-2} + \dots + a_1\times10 + a_0 \\ a_{n-i} \in \{0;1;2;3;4;5;6;7;8;9\}; \quad a_{n-1} \neq 0 $$ We say that $a$ has ...
0
votes
1answer
27 views

Calculating probability of digital roots

I am trying to find correlations in words that share the same single digit digital root. I will assign a correlation if there is the same difference between the n digit digital roots of the words, or ...
5
votes
2answers
55 views

Inifinitely many primes $p\equiv -1 \mod12$

I haven't been able to prove this statement from my Elementary Number course: There are infinitely many primes $p$ such that $p\equiv -1 \mod12$. From here I know that there exists a "Eulcidean ...
0
votes
0answers
16 views

On (known) applications of fixed point theorems to some conjectures in elementary number theory

Let $\sigma$ be the classical sum-of-divisors function. Call an integer $n$ almost perfect if $\sigma(n)=2n-1$. The only known examples are $n=2^k$ for $k \geq 0$. Let $I(n)=\sigma(n)/n$ be the ...
3
votes
4answers
37 views

$\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$?

If $\gcd(N, a)=1$, then we have $\gcd(N, N-a)=1$. More generally, can we have $\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$? Thanks in advance.
1
vote
0answers
50 views

Sum of $m\leq 300$ such that if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$

Find the sum of all the integers $m$ with $1≤m≤300$ such that for any integer $n$ with $n≥2$, if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$. Unfortunately I cannot think of ...
2
votes
2answers
48 views

How to show that $(2, \sqrt{82})$ in $\mathbb{Z}[\sqrt{82}]$ is not pricipal?

I tried the obvious things, like using the norm and trying to show that there were no integer solutions to $a^2 - 82b^2 = 2$, but didn't get anywhere. (A friend asked me this.)
0
votes
2answers
61 views

Integer solutions to $2x^2+5x+y^2=19$

$$2x^2+5x+y^2=19$$ Don't know how to approach the problem. Similar equations required factoring after the completing a square or a similar trick. I don't see the possibility of that here though. ...
2
votes
2answers
28 views

if $4^{\alpha} \equiv k+1 \pmod{2k+1}$ prove there is no $\beta$ where $4^{\beta} \equiv k\pmod{2k+1}$.

Suppose that $3 \nmid 2k+1$ and there is $\alpha$ with $4^{\alpha} \equiv k+1 \pmod{2k+1}$ where $0 \leq \alpha \leq k$. I want to prove that there is no $\beta$, $0\leq \beta \leq k$ such that ...
4
votes
0answers
50 views

theorem relating mersenne numbers?

For $(x2^9)^2=2^q-1+y^2q^2$,where $q$ is prime, is it possible to show that there exists only an unique solution for the pair $\{x,y\}$?
3
votes
4answers
74 views

Proving that $6^{2n+1} + 1$ is divisible by $7$ for $n\geq 1$ by induction

How should I go about solving a problem like this using induction? Would I: First test $(n = 1)$ so that $6^{2(1)+1} + 1 = 6^3 + 1 = 217/7 = 31$. Then assume $(n = k)$ so that you have $6^{2(k) + 1} ...
1
vote
3answers
56 views

Find $y$ satisfying $17y = 1 \mod (130)$

Let $x=17$ $n=130$. Find $y; (1\leq y \leq n-1)$ that satisfies :$$xy=1 \pmod n$$ Now I'm not sure if I should use one of Euler's theorem's for prime numbers? Can anyone help? Or try something with ...
5
votes
2answers
81 views

$3^x + 4^y = 5^z$ [duplicate]

This is an advanced high-school problem. Find all natural $x,y$, and $z$ such that $3^x + 4^y = 5^z$. The only obvious solution I can see is $x=y=z=2$. Are there any other solutions?
1
vote
0answers
22 views

If $q^k n^2$ is an odd perfect number with Euler prime $q$, are the following statements known to hold in general?

(Note: This question has been cross-posted from MO.) Let $\sigma$ be the classical sum-of-divisors function. A number is said to be perfect if $\sigma(N)=2N$. If $q^k n^2$ is an odd perfect number ...
2
votes
0answers
62 views

Help with the results of a test about the distances between primes

I did the following test: For every prime, take the distance $dp$ to the previous prime and the next prime $dn$, then calculate $a=(pp\ mod\ dp)$ and $b=(np\ mod\ dn)$. If $a$ or $b$ $\in \Bbb ...
1
vote
1answer
26 views

If $a \equiv b \mod m$ and $0 \leq a$ and $b < m$, $a=b$?

I was reading Hodel's otherwise excellent An Introduction to Mathematical Logic and, in the appendix on number theory, specifically on the section on congruences, he seems to make a slip. Let $a, b, m ...
3
votes
2answers
28 views

How to tell if a set of simultaneous congruences is solvable?

Let's say we have a set of N simultaneous congruences that looks like this: x ≡ c1 (mod m1) x ≡ c2 (mod m2) ... x ≡ cN (mod mN) Currently, to check if this set has a solution I have to go ...
0
votes
2answers
51 views

A question about Quadratic residue

I need help with this question : Prove that for each prime number p there exist $a,b \in Z$ such that $-1\equiv a^{2}+b^{2}\pmod p $ When $p\equiv1\pmod4$ it is easy because -1 is a quadratic ...
0
votes
1answer
37 views

Find the lowest value of $x$ so that $x \in (A \setminus B)$

Let $A$ and $B$ be two sets for which the following applies: $A = \{x: \text{GCD(}x,12) = 1\}$ $B = \{x: x\ \text{is a prime}\}$ Find the lowest value of $x$ so that $x \in (A \setminus B)$. $x \in ...
2
votes
1answer
63 views

Can the expression $6^{2n} - 25$ be a prime for all $n \geq 2$?

Can the expression $6^{2n} - 25$ be a prime for any $n \geq 2$? My attempt to solve the problem: No, it cannot. $6^{2n} - 25 = (6^{n})^{2} - 25 = (6^{n})^{2} - 5^{2} = (6^{n} + 5)(6^{n} - 5)$ And ...
10
votes
2answers
127 views

Determining if a number is a prime

Consider $$ x = \frac{4^{99}\cdot7 - 1}{3} $$ Is $x$ prime ? Why not ? I tried the divisibility criteria, but I can't find a way. I'm currently dabbling in number theory, but I got stuck on this one. ...
0
votes
2answers
34 views

How to prove the Archimedean property?

The archimedean property states that $$\boxed{~\forall~ ~a,b\in \mathbb{Z}^+~ \exists ~n~|~na\geq b~}$$ I started with disproving .. Suppose $\forall ~\{n,a,b\} \subset \mathbb{Z}^+ , \text{na ...
-1
votes
1answer
28 views

Let $A$ be an uncountable set and let $B$ be a nonempty set. Prove that the cardinality of $A\times B$ is uncountable. [on hold]

If $A$ is an uncountable set and $B$ is a nonempty set, how do I prove that $A\times B$ is uncountable? Also, what is the cardinality of $A-B$? Is it also uncountable?
2
votes
0answers
46 views

On splitting a number as the sum of two squares.

From Lagranges'celebrated four-squares theorem we know that any number is the sum of four squares ( not necessarily nonzero and distinct). But it's an existence theorem and gives no idea of how to ...
2
votes
1answer
57 views

Proof that if $a^3 \mid b^2$ then $a\mid b$. [duplicate]

I am trying to prove that if $a^3 \mid b^2$ then $a\mid b$, where $a,b \in \mathbb{Z}$. Let $PDC(x)$ be the set of all primes in the prime decomposition of $x$. So far, I am using the fundamental ...
1
vote
1answer
23 views

Proving $\gcd(N^a-1,N^b-1)=N^{\gcd(a,b)}-1$.

I have come by one solution only, but things were derived too quickly without me understanding how or why. How does knowing that $\gcd(a,b)$ is a factor and a and b, actually derive that ...
0
votes
1answer
26 views

Show that $a^{p+1\over 4}$ solves the equation $x^2 ≡ a \pmod p$.

Let $p \equiv3 \pmod 4$ be a prime number, and let $1 \le a\le p − 1$ be a quadratic residue. Show that $a^{p+1\over 4}$ solves the equation $x^2 ≡ a \pmod p$. I know that if $(a,n)=1$ and $p\ge ...
6
votes
0answers
58 views
+50

Does there exists a positive $t$ that satisfy this given condition?

I am curious about the validity of my claim concerning the equations: $(2k-1)t+1$ (1) $(2k^2-2k)t+(2k-1)$ (2) where $k=2,3,4,...$ My claim is for almost all $k$ or for infinitely many $k$, there ...
2
votes
2answers
23 views

Set of all integer solutions to a linear diophantine equation

I am trying to figure out the set of all integer solutions in terms of an appropriate number of free variables for the following: $2x_1 + 12x_2 + 3x_3 = 7$. I have found that the $gcd(2,12,3) = 1$ ...
1
vote
3answers
32 views

How to solve a congruence using Fermat's Theorem?

I'm reading Fraleigh's A First Course in Abstract Algebra and I'm trying to understand an example (later I have to solve several problems of the same type). Little Theorem of Fermat: If $a\in ...
3
votes
1answer
29 views

If $q^k n^2$ is an odd perfect number with Euler factor $q^k$, can $q = 73$ hold?

Call a number $N$ perfect if $\sigma(N)=2N$ where $\sigma$ is the classical sum-of-divisors function. If $N = q^k n^2$ is an odd perfect number, can $q = 73$ hold? Here is my attempt: Since ...
2
votes
1answer
61 views

Can any partial harmonic sum be an integer?

There have been a number of posts about the harmonic series, e.g. not being an integer for any number of terms. Edit: Below I try to prove that not only H(n) but also H(2n)-H(n) is not an integer. ...
2
votes
1answer
28 views

What are the most important corollaries/consequences and applications of certain algorithms in elementary number theory? [on hold]

What are the most important corollaries/consequences and applications of Division Algorithm, Euclidean Algorithm and Fundamental Theorem of Arithmetic? I've been studying Elementary Number Theory for ...
1
vote
1answer
19 views

Is it possible to compute $\sigma(AB)$ if $\gcd(A, B) = C > 1$?

Let $\sigma$ be the classical sum-of-divisors function. I know, for one, that $\sigma$ is weakly multiplicative (that is, $\sigma(xy) = \sigma(x)\sigma(y)$ whenever $\gcd(x, y) = 1$). Well, of ...
6
votes
5answers
91 views

Inductively prove that any natural number $\ge 12$ can be written as the sum of 4s and 5s

I can intuitively see why this is true: Let us assume $n = \alpha \times 4 + \beta \times 5$ with $\alpha,\beta \in \mathbb{N} \cup \{0\}$. $\forall n \in \mathbb{N} \cup \{0\}$: $n \div 4$ will ...
0
votes
1answer
22 views

Let $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$, suppose $ax \equiv 1 \mod n$. Prove $a$ is coprime to $n$.

Let $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$, suppose $ax \equiv 1 \mod n$. Prove $a$ is coprime to $n$. How do I do this? I know so far that $ax=1+nk ~(k \in \mathbb{Z})$.
2
votes
2answers
57 views

Finding the solutions of $x^2\equiv 9 \pmod {256}$.

Find the solutions of $x^2\equiv 9 \pmod {256}$. I try to follow an algorithm shown us in class, but I am having troubles doing so. First I have to check how many solutions there are. Since $9\equiv 1 ...
-4
votes
0answers
26 views

How to find two numbers given their sum of squares, HCF and LCM? [on hold]

if sum of squares of two numbers are 2754,HCF is 9,LCM is 135...what are the numbers?
-1
votes
3answers
32 views

How to find two numbers given their difference, HCF and LCM? [on hold]

The difference of two numbers is 14. Their LCM and HCF are 441 and 7 respectively. Find the numbers. Any shortcuts please. Thanks in advance.
3
votes
1answer
31 views

Proof by induction from Spivak's calculus ch 2- 3b

I was cracking my head over the following proof (by induction) from Spivak's calculus. Givens: $ \binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k} $ and $ n \ge k $ Task: Proof by induction that $ ...
3
votes
2answers
26 views

Let $X$ be a set of primes $p$ so that $5^{p^2}+1 \equiv 0 \pmod {p^2}$ Which of these sets is $X$ equal to?

$5^{p^2}+1\equiv 0\pmod {p^2}$ $1.$ $\emptyset $ $2.$ {$3$} $3.$ All primes of the form $4k+3$ $4.$ All primes except $2$ and $5$ $5.$ All primes This one is pretty easy to get right through the ...
1
vote
0answers
15 views

Number of number in range $(l, r)$ satisfying XOR constarint

Here's a questions that's been bugging for some time now: Define the set $S_n = \{k \oplus (k + n)\mid k \in \Bbb Z, k ≥ 0\}$ (here, $\oplus$ is bitwise exclusive OR). To put it another way, $x$ ...
1
vote
2answers
70 views

Why is $ {n\choose k} \equiv 0 \pmod n$ if $n$ is prime? [duplicate]

For all $n>k$, why is: $$ {n\choose k} \equiv 0 \pmod n$$ if $n$ is prime? Any hints anyone? I am really puzzled.
1
vote
2answers
48 views

Legendre symbol, a theoretical question.

I need to show that if $p$ is a prime number of the form $p=4m+1$, then for any divisor $d$ of $m$: $$\left(\frac{d}{p} \right) = 1$$ where $\left(\frac{d}{p} \right)$ is the Legendre symbol. My ...
1
vote
2answers
46 views

Show that the equation $x^2\equiv a \pmod n$ is solvable $\iff$ $a^{\phi (n)\over 2}\equiv 1\pmod n$.

Let $n> 2$ be an integer such that $(\Bbb{Z}/n\Bbb{Z})^*$ has a primitive root. Show that the equation $x^2\equiv a \pmod n$ is solvable $\iff$ $a^{\phi (n)\over 2}\equiv 1\pmod n$. I thought I ...
0
votes
1answer
24 views

Let $n \in \mathbb{N}$ and consider the commutative ring $\mathbb{Z}_n$. Let $a \in \{1,2,…,n-1,n\}$…

Let $n \in \mathbb{N}$ and consider the commutative ring $\mathbb{Z}_n$. Let $a \in \{1,2,...,n-1,n\}$. Suppose $a$ is coprime to $n$ then prove $\bar{a} \in \mathbb{Z}_n$ is a unit. Note ...