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

learn more… | top users | synonyms (1)

-1
votes
0answers
21 views

what is zebloski's number?

I have been searching for quite some time now.this question was an interview question.i am curious.it was asked by a maths professor in an examination.i have googled it and also searched through some ...
3
votes
1answer
38 views

Find all pairs of integers $(a,b),~ b\ne 1$ such that $\frac{a^4-b+1}{ab}$ is an integer

Find all pairs of integers $(a,b)$ such that $\frac{a^4-b+1}{ab}$ is an integer. $b=1$ trivially gives infinitely many solutions as the expression becomes $a^3$. I am not able to find any more ...
107
votes
0answers
6k views
+50

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 ...
1
vote
0answers
5 views

Existence question about Hamming weights of addition of numbers modulo $2^n-1$

Let $w_1, w_2$ be given, $0 \leq w_1, w_2 \leq n-1$. Given an integer $a$, $1 \leq a \leq 2^n-2$, can we find $b$ with $W_H(b) = w_1$ such that $W_H(a + b \mod{2^n-1}) = w_2$? Here $m \mod 2^n-1$ ...
3
votes
1answer
31 views

Prove that the congruence $x^2 \equiv a \mod m$ has a solution if and only if for each prime $p$ dividing $m,$ one of the following conditions holds

Let $m$ be odd and let $a \in \mathbb{Z}.$ The congruence $x^2 \equiv a \mod m$ has a solution if and only if for each prime $p$ dividing $m,$ one of the following conditions holds, where $p^{\alpha} ...
33
votes
2answers
2k views

If the decimal expansion of $a/b$ contains “$7143$” then $b>1250$

I recently stumbled upon this really interesting problem: If we have a fraction $\frac{a}{b}$ where $a,b \in \mathbb{N}$ and we know that the decimal fraction of $\frac{a}{b}$ has the numerical ...
4
votes
1answer
27 views

How do you convert different bases?

I know how to convert any number into base 10 by using the below method. Write (6712)base 8 in base 10. Ans: $6 \times 8^3 + 7 \times 8^2 + 1 \times 8^1 + 2 \times 8^0 = 3530_{10} $ However, I am ...
20
votes
5answers
2k 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 ...
0
votes
1answer
95 views

If $a,b,x,y\in\Bbb N$ , and $ax-by=(a,b)$, then $(x,y)=1$

Need to prove an exercise, and for that I need to show that if $$a,b,x,y\in\Bbb N$$ and $$ax-by=(a,b),$$then$$(x,y)=1.$$ How to do this? I have no idea. Please do not use modular arithmetic.
4
votes
2answers
63 views

$a^2 + b^2$ never leaves remainder $3$ when divided by $4$

Already did something like that to prove the square of an even number Always leaves remainder $1$ when divided by $8$, in which I used induction to arrive at the result. However, I don't know how to ...
0
votes
1answer
25 views

Products of quadratic forms

It is known that, if $x_1^2 + y_1^2 = c_1$ and $x_2^2 + y_2^2 = c_2$, then $(x_1x_2 + y_1y_2)^2 + (x_1y_2 - x_2y_1)^2 = c_1 c_2$ Is there a similar analogue for general quadratic forms $Q(x, y) = ...
3
votes
3answers
44 views

Is there a counterexample? $\forall\ p \gt 3 \in \Bbb P, (number\ of\ Quadratic\ Residues\ mod\ kp)=p\ when\ k\in\{2,3\}$

I have started to learn about the properties of the quadratic residues modulo n (link) and reviewing the list of quadratic residues modulo $n$ $\in [1,n-1]$ I found the following possible property: ...
32
votes
9answers
4k views

How can you prove that the square root of two is irrational?

I have read a few proofs that $\sqrt{2}$ is irrational. I have never, however, been able to really grasp what they were talking about. Is there a simplified proof that $\sqrt{2}$ is irrational?
-1
votes
2answers
38 views

Compute the following GCD

Product of two natural numbers $P$ and $Q$ is $590$ and their GCD is $59$. How many set of values of $P$ and $Q$ is possible? Please provide an explanation along with your answer.
0
votes
2answers
112 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: ...
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
36 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
0answers
37 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
86 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
78 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\}$?
6
votes
4answers
8k 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
72 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 ...
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
39 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
107 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
34 views

Calculating probability of digital roots [on hold]

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
58 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
39 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
112 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
71 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
50 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
17 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
139 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
51 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
66 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
78 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
92 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
30 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 ...
13
votes
7answers
166 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, ...