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

learn more… | top users | synonyms (1)

2
votes
3answers
23 views

For $n > 2, n \in \mathbb{Z}$, show the sum of integers coprime to $n$ in the range $[1,n-1]$ is equal to $\frac{1}{2}n \phi(n)$

For $n > 2, n \in \mathbb{Z}$, show the sum of integers coprime to $n$ in the range $[1,n-1]$ is equal to $\frac{1}{2}n \phi(n)$ Firstly $\phi(n)$ is Euler's totient function, the number of ...
2
votes
1answer
32 views

When is $1+e^{-i\pi(a+b)}+e^{-i\pi(b+c)}+e^{-i\pi(a+c)}$ non-zero, $a$, $b$ and $c$ being integers?

I am trying to find the conditions on the integers $a$, $b$ and $c$ such that $$1+e^{-i\pi(a+b)}+e^{-i\pi(b+c)}+e^{-i\pi(a+c)}$$ is not equal to zero. I think that the conditions for which it is equal ...
0
votes
1answer
14 views

Division of a primorial

What remainder is obtained when the smallest prime number greater than n divides n# ? In other words how do we express n# by Euclid's Division Lemma when the divisor is the smallest prime number ...
-1
votes
0answers
12 views

Please give me some information about primorials [on hold]

Is there any thing of interest about primorials and is there any relation (even slightest) between n# and the smallest prime number greater than n ?
1
vote
2answers
29 views

Find all natural numbers $m,n$ which :$m!+n!+10$ is perfect cube?

I would be interest to invesitigate for all natural numbers $m,n$ which: $m!+n!+10$ is perfect cube ?
3
votes
1answer
25 views

Tiling rectangle with squares using Euclid's algorithm

Is there a proof that tiling an n*m rectangle with squares using Euclid's algorithm (that is always choose the biggest square that fits in the remaining space) results in a minimum sum of the sizes ...
-1
votes
0answers
38 views

what is zebloski's number? [on hold]

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 ...
4
votes
1answer
51 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 ...
2
votes
0answers
16 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 \neq w_2 \leq n-1$. Given an integer $a$, $1 \leq a \leq 2^n-2$, can we find $b$, $0 \leq b \leq 2^n-2$, with $W_H(b) = w_1$ and such that $W_H(a + b \mod{2^n-1}) ...
4
votes
1answer
28 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 ...
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} ...
4
votes
2answers
64 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
26 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) = ...
-1
votes
2answers
39 views

Compute the following GCD [on hold]

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.
34
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 ...
-1
votes
0answers
39 views

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

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..
4
votes
6answers
90 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 ...
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: ...
21
votes
5answers
2k views

Can two perfect squares average to a third perfect square? [duplicate]

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
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
110 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
40 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
56 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
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 ...
5
votes
2answers
79 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
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 ...
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.
1
vote
0answers
52 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
51 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
67 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
31 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 ...
5
votes
1answer
81 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
79 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
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 ...
5
votes
2answers
84 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
24 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 ...
3
votes
0answers
75 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
27 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
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 ...
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
64 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
131 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
29 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
47 views

On splitting a number as the sum of two squares. [duplicate]

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
59 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
80 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 ...