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

learn more… | top users | synonyms (1)

2
votes
3answers
100 views

How can one show the inequality

Let $a,b,n$ be natural numbers (in $\mathbb{N}^*$) such that $a>b$ and $n^2+1=ab$ How can one show that $a-b\geq\sqrt{4n-3}$, and for what values of $n$ equality holds? I tried this: We suppose ...
1
vote
2answers
56 views

Find the value of p, q, r if $\frac{p}{q + r - p} = \frac{q}{p + r - q} = \frac{r}{p + q - r} $

I equated these 3 to k: $\frac{p}{q + r - p} = \frac{q}{p + r - q} = \frac{r}{p + q - r} $ = k and got k=1. After this, $\frac{p}{q + r - p} = k = 1 $, and hence i got: $2p = q + r$ , $2q = p + r$ ...
3
votes
1answer
99 views

Circular definition?

I am new to logic and studying it by Enderton's A Mathematical Introduction to Logic (2nd edition). For question 3.3.1 in the books, which states Show that in the structure $(\mathbb{N}; \cdot, E)$...
8
votes
2answers
112 views

Show $a^p \equiv b^p \mod p^2$

I am looking for a hint on this problem: Suppose $a,b\in\mathbb{N}$ such that $\gcd\{ab,p\}=1$ for a prime $p$. Show that if $a^p\equiv b^p \pmod p$, then we have: $$a^p \equiv b^p \pmod {p^2}.$$ ...
3
votes
1answer
63 views

Primes, congruence mod4, odd exponents, sum of two squares

I am trying to prove: (T) If a prime $p$ is congruent to $3 \bmod 4$ and it occurs with an odd exponent in the prime factorization of $n\in\mathbb N$, then $n$ is not a sum of two squares. I have ...
1
vote
2answers
34 views

Congruence arithmetic proof of $2i \equiv 2j \pmod{2m}$ implies $i \equiv j \pmod{2m}$ or $i\equiv j + m \pmod{2m}$.

If $2i \equiv 2j \pmod{2m}$, then either $i \equiv j \pmod{2m}$ or $i + m \equiv j \pmod{2m}$. This is easy to show by using the definition, i.e. if $2m$ divides $2(i-j)$, then either $2m$ divides $(i-...
5
votes
1answer
69 views

About the decimal period of $\frac 17$

It is easy to verify that $$\frac 17=\frac {142857}{999999}$$ where $142857$ is the decimal period of $\frac 17$. This period, which has six different digits, has the property that when multiplied ...
1
vote
0answers
51 views

positive integer composite numbers $ n $ such that $ n $ divides $ 3 ^ {n-1} - 2 ^{n-1} $

Prove that exist infinite positive integer composite numbers $ n $ such that $ n $ divides $ 3 ^ {n-1} - 2 ^{n-1} $
2
votes
1answer
46 views

Show that $r$ is a primitive root (mod $p^k$)

Let $p$ be an odd prime, and let $r$ be a primitive root (mod $p$) such that $r^{p-1} \neq 1$ (mod $p^2$). Show that $r$ is a primitive root (mod $p^k$) for all $k \geq 1$. So I start of by computing ...
3
votes
2answers
213 views

Why are most divisibility exercises only for positive integers?

I've been doing some exercises and most of them are about positive integers. Here are a few examples: (1) Show that if $a,b$ are positive integers then $ab = \gcd(a,b) \text{lcm}(a,b)$. (2) Let $a,b$...
0
votes
0answers
23 views

Repeated squaring vs. regular modular exponentiation

I initially thought I would use repeated squaring for computations of the for $a^b \ mod \ c$ for large values of $a$ and $c$. Is there a better way to decide?
0
votes
1answer
30 views

find the relation between $A$ and $G$.

If A and G ar A.M. and G.M. and $x^2-2Ax+G^2=0$ then find the relation between $A$ and $G$. The answer is $A>G$ but I couldn't understand why its always true.Please help.
3
votes
3answers
92 views

Computing $7$th root of $2$ modulo $33$

$\varphi(33) = 20$ $ed = 1 \pmod {20}$, and $d$ is $7$, so $e$ is $3$. $(3 \times 7 \mod 20 \equiv 1)$ So $x^e \pmod {33}$ is the seventh root. But how do you compute $x$? Later: My error was ...
0
votes
1answer
117 views

What does auxiliary prime mean?

I'm writing a paper right now, in which Sophie Germain's theorem is included. Can anybody explain auxiliary prime θ to me? Context: Sophie Germain proved that the product $xyz$ must be divisible by ...
5
votes
5answers
831 views

Prime factors of a factorial [closed]

Determine all (distinct) prime factors of $1000!$. Here we seek a description of these factors as a set; there is no need to compute them. What exactly do I need to determine here?
7
votes
2answers
141 views

Prove that if $7^n-3^n$ is divisible by $n>1$, then $n$ must be even.

I tried using factorization of $a^n-b^n$ for odd $n$ in an attempt to work through to a situation where the factors are such that they cannot have n as a factor. But I reached nowhere. Here's how I ...
2
votes
2answers
51 views

Suppose $n|a^2-1$ Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$

Suppose $n|a^2-1$ where $a>1$ and n is odd. Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$. Part 2 Show that if $a<n-1$ then this gives a nontrivial factorization of n What I did: I found the gcd$(a-...
2
votes
1answer
62 views

When is sum of first $n$ natural numbers a square? [duplicate]

My question is: When is $\sum_{i=1}^n i$ a square number? I know that this means i have to solve $n(n+1)/2=m^2$. I tried with modulo 2 etc. but i don't get to it. Please help.
-1
votes
2answers
98 views

$x^4 = -1$ (mod $p$) implies p = 1 mod 8

Let $p$ be an odd prime. Show that $x^4 = -1$ (mod $p$) has a solution if and only if $\Leftrightarrow p = 1$ (mod $8$)
1
vote
3answers
60 views

How to see that $\text{gcd}(a,b) = \text{gcd}(a-b,b)$?

I'm trying to understand why $\text{gcd}(a,b) = \text{gcd}(a-b,b)$. What is clear to me is that the $\text{gcd}$ divides $a,b$ and also $a-b$ (let's assume $a\ge b$). But then it seems to me we ...
1
vote
1answer
33 views

Let $a,b,m,n \in N$ with $\gcd(m,n)=1$ prove that the modular system $ \{ x=a \mod m ; x =b\mod n \}$ has absolution and is unique modulo $mn$}

Let $a,b,m,n \in N$ with $\gcd(m,n)=1$ prove that the modular system $ \{ x=a \mod m ; x =b\mod n \}$ has absolution and is unique modulo $mn$} Note that had asked a question I got why there it is ...
3
votes
1answer
45 views

Primitive Root Modulo $p=4q+1$

Let $p$ and $q$ be primes such that $p=4q+1$. Then $2$ is a primitive root modulo $p$. Proof. Note that $q\not=2$ since $4\cdot2+1=9$ is not prime. $\mathrm{ord}_p(2)\vert p-1=4q$, so $\mathrm{ord}...
0
votes
0answers
38 views

Help proving a lemma about existence of $n$ so that $n\text{ mod }m \in (a,b)$.

I'm trying to prove the following lemma: We have $m$ is a real number greater than 1, and an open interval $(a, b) \subseteq [0, m)$ with $a < b$. Then if $n\text{ mod } m \in (a, b)$ for some ...
0
votes
0answers
42 views

Legendre symbol of $-n$

Let $x, y, n, p$ be positive integers such that $x^2 + ny^2 = p$, where $p$ is a prime such that $p \neq n$. Show that the Legendre symbol $(-n/p) = 1$.
0
votes
0answers
27 views

Properties/Significance of the Radical (Square-free kernel) of an integer

The radical, or square-free kernel, of an integer is the product of its distinct prime factors. So that if $n=\prod_{i=1}^{s} p_i^{\alpha_i}$ is a prime decomposition of $n$ then the radical of $n$ ...
0
votes
0answers
13 views

Inequalities Implying a Value of Jacobsthal's Function

Jacobsthal's function $g\colon\mathbb N\to\mathbb N$ is defined by letting $g(n)$ be the smallest positive integer $\ell$ such that any set of $\ell$ consecutive integers must include some element ...
2
votes
1answer
54 views

$3^x-2^y=1$, $x \in \mathbb{N}$ and $y \in \mathbb{N}$

$3^x-2^y=1$ or $y=\log_2{\left(3^x-1\right)}$ $x$ and $y$ must be natural numbers. I know this two solutions: $x=1$ and $y=1$ $x=2$ and $y=3$ Are there more solutions? How can I find them?
0
votes
3answers
49 views

Question to find the value of P in following question [closed]

Let $a, b$ and $c$ be such that $$a + b + c = 0 \qquad\text{and}\qquad P = \frac{a^2}{2a^2 + bc} + \frac{b^2}{2b^2 + ca} + \frac{c^2}{2c^2 + ab}.$$ How could I find Integral value of $P$.
7
votes
1answer
107 views

Pairwise sums are perfect squares .

I thought of this problem as a simplification of the Euler-Brick problem . $1)$For which $n$ is it possible to find $n$ distinct positive integers $a_1,a_2,\ldots,a_n$ such that all their pairwise ...
1
vote
1answer
22 views

How did the author get at $z = -(|a|+1)$ in the proof of division theorem?

Theorem Let $a,n \in Z$ with $n \neq 0$. There are $q,r \in Z$ with $a = nq+r$ and $0 \leq r < |n|$, and both $q$ and $r$ are unique with these properties. Proof The author intends to prove the ...
0
votes
1answer
30 views

Does every congruence class modulo m has an inverse pairing?

For example for mod 11 I get that all the congruence classes of it has an inverse pairing: 1 (mod 11) and itself, 10 (mod 11) and itself, 2 (mod 11) and 6 (mod 11), 3 (mod 11) and 4 (mod 11), 5 (mod ...
2
votes
2answers
64 views

Divisibility of $2^n-n^2$ by 7

How many positive integers $n<10^4$ are there such that $2^n - n^2$ is divisible by 7?
1
vote
0answers
42 views

How to prove by induction the formula to find LCM of two numbers for multiple numbers?

There exist a formula to easily find the least common multiple of 2 integers: $$ \operatorname{lcm}(x,y)=\frac {x\cdot y}{\gcd(x,y)} $$ And for multiple numbers: $$ \operatorname{lcm}(a_1, a_2, ...
2
votes
1answer
53 views

Triangular numbers that are semiprime

Is it trivial that the the triangular numbers that are semiprime are odd, with the exceptions of 6 and 10? This question is related to the following two sequences: https://oeis.org/A068443 ...
1
vote
0answers
135 views

Modular arithmetic and Fermat's Last Theorem.

I have an assignment, and two of the questions are bugging me. Show that in the equation $$x^n + y^n =z^n$$ have a (non-trivial) whole number solution, so $$x^n + y^n =z^n \pmod p$$ for a prime ...
6
votes
5answers
328 views

Is $(-2)^{\sqrt{2}}$ a real number?

Is $(-2)^{\sqrt{2}}$ a real number? Clarification: Is there some reason why $(-2)^{\sqrt{2}}$ is not a real number because it doesn't make sense why it shouldn't be a real number. Mathematically we ...
4
votes
2answers
53 views

Proof by contrapositive: $ 4 \nmid (n-2)^2 \implies 6 \nmid n $

Prove: $ 4 \nmid (n-2)^2 \implies 6 \nmid n $ Proof by contrapositive: $ 6 \mid n \implies 4 \mid (n-2)^2 $ $n=6k,$ $ k \in \mathbb Z $ $((6k)-2)^2 = 36k^2 - 24k+4 = 4(9k^2 - 6k+1), (n-2)^2=4c$ ...
0
votes
3answers
54 views

Computation of residue class of $2^{100}$ modulo $1000$

$2^{100} \equiv 1 \ (\text{mod}\ 125)$ and is divisible by $8$. Why then is $2^{100} \equiv 376 \ (\text{mod}\ 1000)$?
3
votes
1answer
37 views

Would this sequence (OEIS A068374) be somehow attached to the twin prime conjecture?

Today I came across an interesting sequence at OEIS, A068374, described as "Primes $n$ such that positive values of $n$-Primorial($k$) are all primes ($k\gt0$)". The sequence is as follows: $(2, 5, ...
25
votes
8answers
658 views

Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$

Prove that $$(n!)\cdot(m!)^n|(mn)!$$ I can prove it using Legendre's Formula, but I have to use the lemma that $$ \dfrac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{...
5
votes
3answers
75 views

What is the least number of digits in $n$?

A positive integer $n$ is multiplied by $7$. The resulting product contains just one digit repeated several times, and that digit is not $7$. What is the least number of digits in $n$? I can only ...
2
votes
0answers
33 views

What does the equation $a^{-k} \pmod N$ or $a^{k+1} \pmod N$ do when $N$ is composite and $N = 4k+3$?

I was studying what the equation $a^{-k} \pmod p$ and $a^{k+1} \pmod p$ when $p$ is prime. It is not hard to show that both of those are square roots of $a$ in this special case. In this special case ...
1
vote
1answer
50 views

How many solution has the quadratic equation $x^2 \equiv a \pmod N$ when $N=pq$ and what is the proof?

I wanted to know how many solutions the quadratic equation: $$x^2 \equiv a \pmod N$$ had when $N$ is a composite of the form $N = pq$. It is not too hard to show that when $N$ is prime, there are ...
0
votes
1answer
34 views

Meaning of the Corollary 31.29 of the Chinese Remainder Theorem

I was reading CLRS and it had the following Corollary: If $n_1, n_2, ..., n_k$ are pairwise relatively prime and $n = n_1n_2...n_k$ then for all integers $x$ and $a$, $$ x \equiv a \pmod {...
2
votes
5answers
109 views

True or false: There is no square $6$ mod $7$.

True or false: There is no square $6$ mod $7$. If you find an example, then you are finish. If you cannot find an example, then prove that the below statement is not true. $$ x^2 \equiv 6\mod 7$$ ...
0
votes
3answers
30 views

Problem on conditions on the divisors of integers

I've recently started exploring elementary number theory, and came across the book Number Theory for Beginners by André Weil, which is where I found this problem. The problem is: Prove that any ...
3
votes
0answers
46 views

Compute sum over bounded numbers prime with given number

When I was doing some task of analytic number theory I was stuck on computing this sum $$S:=\frac{1}{L} \sum_{q \in \mathcal{Q}} \phi(q) \overline{a}^{\frac{1}{2}},$$ where $\overline{a}$ is the ...
2
votes
2answers
54 views

Is the relation $a $~$ b$ iff $ ab$ is square on $\mathbb{Z}$ transitive?

I'm trying to determine whether the relation given above is a equivalence relation. I've already proved it is reflexive and symmetric, but I'm stuck trying to prove (or disprove) its transitivity. I ...
4
votes
1answer
154 views

$A \in M_3(\mathbb Z)$ be such that $\det(A)=1$ ; then what is the maximum possible number of entries of $A$ that are even ?

Let $A \in M_3(\mathbb Z)$ be such that $\det(A)=1$ ; then what is the maximum possible number of entries of $A$ that are even ?
9
votes
2answers
536 views

Infinitude of primes in 10 consecutive integers

Do there exist infinitely many sets of 10 consecutive positive integers where exactly one is a prime? By Dirichlet's Theorem, if $a$ and $d$ are relatively prime, then there infinitely many primes ...