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

learn more… | top users | synonyms (1)

0
votes
2answers
288 views

The system of genus characters determined by a binary quadratic form

Let $f = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. Let $D = b^2 -4ac$ be its discriminant. It is easy to see that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). We suppose ...
2
votes
1answer
30 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 ...
0
votes
0answers
23 views

If $m^n -m=(m-n)!$, where m>n>1 and $ m=n^2$, then the value of $m^2 +n^2 =?$

If $m^n -m=(m-n)!$, where m>n>1 and $ m=n^2$, then $m^2 +n^2 =?$ how can I find this one ?? I found ridiculous after some stapes..
3
votes
6answers
72 views

Last 2 digits of $9^{1500}$

I've read this PDF where it explains how to find the last digit of a number. If I were to find the last digit of $9^{1500}$ I would simply write it as $(3^{2})^{1500}$ and then use the patterns in ...
5
votes
1answer
68 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\}$?
15
votes
3answers
791 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 ...
6
votes
4answers
7k views

How many positive integers are factors of a given number?

I've been trying to find / generate a formula for the following problem: Given a number, how many positive integers are factors of this number. In practice, you could simply build a table as such ...
3
votes
0answers
69 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 ...
0
votes
2answers
107 views

Congruence with variable modulus

I have been working on some problems and one of them has been particularly challenging. The problem is as follows. Find a non-trivial (meaning more than 1 digit) positive integer a that satisfies: ...
3
votes
1answer
58 views

prime divisor propertyfor Hurwitz integers

The Hurwitz integers $\mathcal{H}_{\mathbb{Z}}$ is a particular subset of quaternions. Define: $$ \mathcal{H}_{\mathbb{Z}} = \left\{ a\frac{1+i+j+k}{2}+bi+cj+dk \ | \ a,b,c,d \in \mathbb{Z} \right\} = ...
4
votes
0answers
125 views

What is stopping every Mordell equation from having a [truly] elementary proof?

The Mordell equation is the Diophantine equation $$Y^2 = X^3-k \tag{1}$$ where $k$ is a given integer. There is no known single method — elementary or otherwise — to solve equation $(1)$ for all $k$, ...
2
votes
1answer
38 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
101 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 ...
0
votes
1answer
30 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 ...
-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 ...
2
votes
2answers
64 views

How to prove that $(p-1)^2$ $\mid$ $(p-1)!$ when $p$ is a prime number and $p>5$?

I say that $p-1$ $\mid$ $(p-1)!$ then I want to prove that $p-1$ $\mid$ $(p-2)!$. I started by saying that $p-1$ is an even number so $2\mid (p-1)$ and that means that $\frac{p-1}{2}$ is an integer. ...
5
votes
4answers
2k views

Proof By Induction Divisibility Question: $12\mid 3^n + 7^{n-1} + 8$

Prove that $3^n + 7^{n-1} + 8$ is divisible by $12$ for all positive integers $n$. I have proved it is true for $n=1$ and I have done the 'assume $n=k$' step, but after getting $3^{k+1} + 7^k + 8$, I ...
0
votes
3answers
173 views

Euclidean algorithm for $\gcd(60,17)$

Hay I am going over some old exams and hit this: (a) Use the Euclidean algorithm to show that $\gcd(60; 17) = 1$. (b) Hence find integers $x, y$ satisfying $60x + 17y = 1$. (c) Find ...
0
votes
0answers
19 views

If the euclidean algorithm is used to solve an equation ( i.e., $ax = b \mod(z)$) is the solution unique?

I have solved such an equation using the euclidean algorithm. However, unlike other methods, this gives one solution. Is this just one solution or the only solution. Help is much appreciated. Thank ...
1
vote
3answers
57 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 ...
3
votes
4answers
38 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.
3
votes
8answers
111 views

Proving that $12^n + 2(5^{n-1})$ is a multiple of 7 for $n\geq 1$ by induction

Prove by induction that $12^n + 2(5^{n-1})$ is a multiple of $7$. Here's where I am right now: Assume $n= k $ is correct: $$12^k+2(5^{k-1}) = 7k.$$ Let $n= k+1 $: $$12^{k+1} + 2(5^k)$$ ...
6
votes
7answers
137 views

How to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction?

I want to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction. My first step is replace $n$ with $1$. $2^{1+2}+3^{2(1)+1}$ $2^3+3^3$ $8+27$ $35 = 7\times 5$ The next step is assume ...
3
votes
4answers
78 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} ...
4
votes
3answers
137 views

Is my intuition of “If $p \mid ab$ then $p \mid a$ or $p \mid b$” correct?

I'm studying number theory and I was given this Theorem to look at: If $p \mid ab$ then $p \mid a$ or $p \mid b$ I had the following intuition for the problem or a proof of sorts if you will. ...
5
votes
2answers
56 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 ...
2
votes
2answers
49 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
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 ...
4
votes
1answer
138 views

Pairwise prime triples of integers satisfying $x^2+y^2=z^2$

The following property has been stated without proof in a problem solving book (not as a problem, hence no solution). I also looked at the number theory text I have, and I cannot find it. All ...
3
votes
1answer
148 views

$x^4+5y^4=z^2$ doesn't have an integer solution.

I hope to show that $x^4+5y^4=z^2$ doesn't have an integer solution. You may guess that you can solve it using the infinite descent procedure. I tried it but I had a trouble in solving it. What I ...
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 ...
0
votes
2answers
64 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. ...
6
votes
0answers
65 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 ...
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 ...
2
votes
2answers
30 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 ...
3
votes
2answers
29 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 ...
104
votes
0answers
6k views

A variation of Fermat's little theorem

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
13
votes
7answers
163 views

What are statements about the natural numbers where induction is impossible or unnecessary to prove?

I'm looking for statements like "for all natural numbers, ____" where induction would be impossible or unnecessarily complicated. This is for pedagogical reasons. When students first learn induction, ...
7
votes
1answer
45 views

Infinite solutions for $(\frac{n+1}{n})^a\cdot (\frac{m+1}{m})^b = 2$

Given $(\frac{n+1}{n})^a\cdot (\frac{m+1}{m})^b = 2$ where a, b, n, and m are all positive integers, are there infinitely many solutions $(a,b,n,m)$?
5
votes
2answers
83 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?
2
votes
1answer
82 views

Improving the bound $q < n\sqrt{3}$ for an odd perfect number $N = {q^k}{n^2}$ given in Eulerian form

(Note: This has been cross-posted to MO.) Let $N = {q^k}{n^2}$ be an odd perfect number given in Eulerian form (i.e., $q$ is prime with $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q, n) = 1$). ...
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 ...
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 ...
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
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. ...
10
votes
2answers
130 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. ...
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 ...
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
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?