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

learn more… | top users | synonyms (1)

0
votes
2answers
13 views

Looking for reading material on: Numbers, in whose internal decimal places appear all natural numbers as a sequence of digits

For example one can have the number 0.12 and can look at the sequence of the digits of it's internal decimal places and see, that 0.12 contains the numbers 1,2 and 12. It is also easy to construct a ...
0
votes
0answers
13 views

Prove that there is a 1-1 correspondence between all of the divisors of n which are not less than square root of n

"Prove that there is a 1-1 correspondence between all of the divisors of n which are not less than square root of n and all the ways of writing n as a difference of two squares of nonnegative ...
2
votes
3answers
25 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
30 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
1answer
21 views

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

Let $w_1, w_2$ be given, $1 \leq w_1 \neq w_2 \leq n-1$. Given an integer $a$, $1 \leq a \leq 2^n-2$, can we find $b$, $1 \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
65 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
27 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
68 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
59 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 ...