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

learn more… | top users | synonyms (1)

1
vote
3answers
101 views

Fibonacci series in 0-Even-Odd-Even-Odd-N series up to N

Another question from the test for the Normale of Pisa: Consider the series $S_n$ of integer numbers repeteandly even - odd - even - odd that start with 0 and finish with n, so with n = 3 we get 2 ...
0
votes
3answers
195 views

Coprime numbers - number theory

If there is a finite set of $k$ integers how can I prove that there is a coprime for each number in the set? That is pretty obvious but what is the formal way to prove this?
6
votes
1answer
86 views

Solve $2a^b-b=1997$ in $\mathbb{N}$

Problem. Find all pairs of positive integers $a$ and $b$ such that the following equality holds: $$2a^b-b=1997.$$ My attempt. We see that $b$ has to be odd, and that $L=(1997+b)/2$ has to be ...
-1
votes
2answers
88 views

Solve $x^2 \equiv 29\pmod {35}$

What are the solutions of the congruence $x^2 \equiv 29\pmod {35}$. Use congruence modulo $5$ and modulo $7$.
1
vote
1answer
720 views

Proving that $C$ is a subset of $f^{-1}[f(C)]$

More homework help. Given the function $f:A \to B$. Let $C$ be a subset of $A$ and let $D$ be a subset of $B$. Prove that: $C$ is a subset of $f^{-1}[f(C)]$ So I have to show that every element ...
2
votes
1answer
88 views

Cubes, squares and minimal sums

I have trouble solving the following task: i need to find positive integers a and b such that 1) $a \neq b$ 2) $ \exists c \in \mathbb{N} : ~ a^2 + b^2 = c^3$ 3) $\exists d \in \mathbb{N}: ~ a^3 + ...
6
votes
1answer
96 views

How to prove $\sum_{i=1}^{n-1}\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}\lt1$ where $a_i\in\mathbb N$ and $a_i\lt a_{i+1}$?

Let $a_1,a_2,\ldots ,a_n\in\mathbb N$ and $a_1\lt a_2\lt\cdots\lt a_n$. Then how to prove $$\sum_{i=1}^{n-1}\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}\lt1$$ Thanks in advance
1
vote
1answer
57 views

Showing that if $p = k2^n+1$ with $k$ odd, then the Jacobi symbol $(\frac{k}{p})$ equals $1$

I am observing if $p = k2^n+1$ (a Proth number), $k$ is odd, there is always an integer $x$, such that $k = x^2 \bmod p$, i.e. the Jacobi symbol $(\frac{k}{p})$ is always $1$. Can someone give a ...
2
votes
1answer
73 views

Maximal sum of positive numbers

I'll be grateful for any help with the foollowing question. I think the solution must be easy enough but i haven't figured it out yet. Let a and b be positive integers such that 1) $\exists c \in ...
10
votes
3answers
419 views

Integer solutions for $x^3+2=y^2$?

I've heard a famous result that $26$ is the only integer, such that $26-1=25$ is a square number and $26+1=27$ is a cubic number.In other words, $(x,y)=(5,3)$ is the only solution for $x^2+2=y^3$. ...
0
votes
3answers
61 views

Groups and primitive roots

How can I prove that $48$ belongs to the group $Z_{385} ^*$? and then how do I find the order of $48$ in this group? I just need some guidance I have no idea what to use in here.
-1
votes
2answers
78 views

How to solve this equation for $y$? Is it an irrational number or rational?

How to solve this equation for $y$? and is it an irrational number or a rational? $$\frac{2}{7}\pi^2\log2+\frac{16}{7}\int_{0}^{\frac{\pi}{2}}x\log(\sin x)\,\mathrm{d}x-\sqrt{y}\pi^3=0.$$
1
vote
1answer
51 views

Proving that if $a$ is a primitive root mod $p$, then $a$ or $a+p$ is a primitive root mod $p^2$

Let $a$ be a primitive root mod $p$. Prove that $a$ or $a+p$ is a primitive root mod $p^2$. This is what I did so far: $\phi(p^2)=p^2-p=p(p-1)$. $(a+p)^{p-1}=a^{p-1} +(p-1)a^{p-2}p ...
6
votes
1answer
88 views

Find the floor value of a finite continued surd

Given $x=20062007$, and let $$A=\sqrt{x^2+\sqrt{4x^2+\sqrt{16x^2+\sqrt{100x^2+39x+\sqrt{3}}}}}.$$ Find the greatest integer not exceeding $A$.
2
votes
1answer
57 views

Number of solutions to $z^2 \equiv p^fb \pmod{p^e}$?

Let $p$ be an odd prime, and let $e \in \mathbb{Z}$ with $e>1$. Let $a$ be an integer of the form $a = p^fb$, where $0 \leq f< e$ and $p \nmid b$. Consider the integer solutions $z$ to the ...
4
votes
2answers
173 views

Foundation on Diophantine Analysis and Number Theory

I want to read particularly about diophantine Analysis and Elementary Number Theory from a novice level. The books which I found on net: A Guide to Elementary Number Theory by Underwood Dudley ...
4
votes
6answers
1k views

What is the remainder when $25^{889}$ is divided by 99?

What is the remainder when $25^{889}$ is divided by 99 ? $25^3$ divided by $99$ gives $26$ as a remainder. $25*(25^3)$ divided by $99$ gives (remainder when $25*26$ is divided by $99$) as a ...
-1
votes
1answer
235 views

Number theory - Primitive root of $338$ [closed]

Im having problem $338$ root. I know it has a root because $13^2\times2=338$ but what is the correct way to find it??
1
vote
2answers
88 views

Determining the order of $-a$ if $a$ is a primitive root

Let $p$ be a prime such that $p\equiv1\pmod4$. Prove that $a$ is a primitive root modulo $p$ if and only if $-a$ is a primitive root mod $p$. Let $p$ be a prime such that $p\equiv3\pmod4$. ...
1
vote
1answer
52 views

Showing that if $p_1\equiv p_2 \pmod{4n}$, then $(\frac{n}{p_1})=(\frac{n}{p2})$

Let $n$ be an integer and $p_1$, $p_2$ be primes such that $p_1 \equiv p_2 \pmod{4n}$. Prove $\left(\dfrac{n}{p_1}\right)=\left(\dfrac{n}{p_2}\right)$. 2 cases: $p_1=4nk_1+1$, $p_2=4nk_2+1$. ...
2
votes
3answers
108 views

Proving that every set $A \subset \Bbb N$ of size $n$ contains a subset $B \subset A$ with $n | \sum_{b \in B} b$

If $n\in \Bbb N$, $A\subset \Bbb N$, $|A|=n$, how to prove that there exists a subset of $A$ such that the summation of its element is divisible by $n$?
7
votes
3answers
305 views

Proving there are no integers $a, b, c$ satisfying $12a + 18b + 27c = 227$

Given $12a + 18b + 27c = 227$, how can we prove that $a, b, c$ can never be integers? I don't have many ideas. Can someone give me some ideas?
2
votes
6answers
236 views

Proving that $\gcd(5^{98} + 3, \; 5^{99} + 1) = 14$

Prove that $\gcd(5^{98} + 3, \; 5^{99} + 1) = 14$. I know that for proving the $\gcd(a,b) = c$ you need to prove $c|a$ and $c|b$ $c$ is the greatest number that divides $a$ and $b$ Number 2 ...
2
votes
1answer
262 views

For what primes $p$ does the series $1!+2!+3!+4!+ \cdots $ converge $p$-adically?

this is a question from a book I'm struggling with, please could you provide a clear proof For what primes p does the series $1!+2!+3!+4!+ \cdots $ converge $p$-adically? kind thanks
1
vote
2answers
190 views

Compute the $p$-adic order of $(p^n)! = p^n (p^n − 1) (p^n − 2) \cdots (2) 1$.

This is a question from a book I'm struggling with, please could you provide a clear proof? Compute the $p$-adic order of $(p^n)! = p^n (p^n − 1) (p^n − 2) \cdots (2) 1$. kind thanks
0
votes
1answer
71 views

For which primes p does the series $\sum_{i=0}^\infty (\frac{10}{11})^i$ converge p-adically

For which primes p does the series $\sum_{i=0}^\infty (\frac{10}{11})^i$ converge p-adically and, when it does, to what limit?
0
votes
2answers
98 views

$\operatorname{lcm}(\operatorname{gcd}(a,b),c)=\operatorname{gcd}(\operatorname{lcm}(a,c),\operatorname{lcm}(b,c))$ for any $a,b,c \in \mathbb{Z}$

I tried to show that the lattice of subgroups of the group $\mathbb{Z}$ is distributive. The question reduced showing that for any $a,b,c \in \mathbb{Z}$ we have that $$ ...
2
votes
2answers
187 views

Which integers can be expressed as a sum of squares of two coprime integers?

I want to find integers $z=a^2+b^2$ with $\gcd(a,b)=1$. Clearly all prime numbers of the form $4k+1$ are such numbers, but what other composite numbers also enjoy this property? e.g. $74=5^2+7^2$, ...
0
votes
2answers
648 views

Proof by induction that $n^3 - n$ is divisible by $6$

Show using induction that $n^3-n$ is divisible by 6 $\forall n\ge1, \quad n \in \mathbb{N}$ First off i show that the basis step: $1^3-1=0, \quad \frac{0}{6}=0$ Now I factorised it and set it ...
3
votes
4answers
2k views

Proof by induction; $a^n$ divides $b^n$ implies $a$ divides $b$

I want to prove by induction that $a^n \mid b^n$ implies that $a \mid b$ holds for all integers $n\geq 1$. clearly for $n=1$ this is true, since if $a \mid b$, then $a \mid b$. Suppose this is true ...
3
votes
2answers
177 views

Proving there is a primitive root mod $p$ such that $a^{p-1} \not\equiv 1 \pmod{p^2}$

Prove there is a primitive root mod $p$ such that $a^{p-1} \not\equiv 1 \pmod{p^2}$. ($p$ is an odd prime.) I don't know how to start this question.
1
vote
5answers
1k views

Solutions of the congruence $x^2 \equiv 1 \pmod{m}$

For $m>2$, if a primitive root modulo $m$ exists, prove that the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv 1 \pmod m$ and $x \equiv -1 \pmod m$. Thanks.
3
votes
9answers
1k views

Prove that $n^2 + n +1$ is not divisible by $5$ for any $n$

Prove that $n^2 + n +1$ is not divisible by $5$ for any $n$. I believe this might be tried using division algorithm, or modular arithmetic. I don't see exactly how to start this... Please help.
1
vote
2answers
222 views

Creating the set of natural numbers

I am not a mathematician but an engineer, so I can read some basics of the language proofs are written in. Second I am bad in probability and infinity and my question covers both. So I like to ...
0
votes
1answer
88 views

Proving there is an $a$ that is not a quadratic residue mod $p$ for any prime $2 < p \leq 1000$

Prove there is an integer $a$ such that for all primes $p$ between $2$ and $1000$, the number $a$ is not a quadratic residue mod $p$. Thanks.
2
votes
2answers
77 views

Determining if there is a solution to $2004x^2+2005y=1$ for integers $x,y$

I have an equation and need to decide if there is a solution to $$2004x^2+2005y=1,$$ where $x$ and $y$ are integers. A clue: $2005=5\cdot401$ and $401$ is a prime number. How to start question like ...
4
votes
2answers
170 views

Can twice a perfect square be divisible by $q^{\frac{q+1}{2}} + 1$, where $q$ is a prime with $q \equiv 1 \pmod 4$?

Can twice a perfect square be divisible by $$q^{\frac{q+1}{2}} + 1,$$ where $q$ is a prime with $q \equiv 1 \pmod 4$?
0
votes
2answers
146 views

Quicker Way to Compute Modulus?

Are there any tricks associated with finding a large value $mod$ another value? I'm working on problems that involve computing the Legendre symbol value and need to take the modulus of another prime ...
0
votes
3answers
269 views

Finding the remainder after dividing $2^{2^{17}} + 1$ by $19$

Can you please give me any hints for finding the modulo of the division of $\large \displaystyle 2^{2^{17}} + 1$ with the number $19$. Thank you.
0
votes
3answers
97 views

Find the solutions of system of equivalences for modulo

Can you please help me solve the system of equivalences: $x \equiv 3 \pmod {13}$ and $x \equiv 3 \pmod {17}$ and $x \equiv 13 \pmod {23}$ Thank you!
2
votes
5answers
287 views

Finding solutions of the system $27x + 90 \equiv 18 \pmod{99}$

I have to find solutions for the expression $$27x + 90 \equiv 18 \pmod{99}$$ My only problem is that I can only solve expressions like $ax \equiv b \pmod{n}$. How can I get rid of the $90$? ...
4
votes
4answers
121 views

Proving $\gcd(n^2(n^2+1),2n+1)=\gcd(2n+1,5)$

We suppose $\forall n \in \mathbb {N}\setminus{0}$. How can I prove that $\gcd(n^2(n^2+1),2n+1)=\gcd(2n+1,5)$?
2
votes
2answers
356 views

Finding all quadratic residues

$p$ is an odd prime. $a$ is a primitive root mod $p$. Prove that the quadratic residues mod $p$ are $a^{2i}$ when $0 \leq i \leq (p-1)/2$. What I know is that $a^{2i}$ are always quadratic ...
2
votes
3answers
70 views

Showing that $3^{(p+1)/4}$ satisfies $x^2 \equiv 3 \mod p$ for primes $p\equiv11 \mod 12$

Let $p$ a prime with $p\equiv11 \mod 12$. I have to prove that $3^{(p+1)/4}$ is a solution to $x^2\equiv3\mod p$. This is how I start: There is a solution because $p\equiv11 \mod 12 \Rightarrow ...
8
votes
4answers
9k views

How do the floor and ceiling functions work on negative numbers?

It's clear to me how these functions work on positive real numbers: you round up or down accordingly. But if you have to round a negative real number: to take $\,-0.8\,$ to $\,-1,\,$ then do you take ...
7
votes
5answers
179 views

Find remainder of $F_n$ when divided by $5$

Let $\{ F_n\}$ be the sequence of numbers defined by $F_1=1=F_2;\, F_{n+1}=F_n+F_{n-1}$ for $n \geq 2$. Let $f_n$ be the remainder left when $F_n$ is divided by $5$. Then $f_{2000}$ equals ...
1
vote
5answers
196 views

To prove a property of greatest common divisor

Suppose integer $d$ is the greatest common divisor of integer $a$ and $b$, how to prove, there exist whole number $r$ and $s$, so that $$d = r \cdot a + s \cdot b $$ ? i know a proof in abstract ...
0
votes
4answers
108 views

Number of distinct prime divisors given $\phi(n)$

Suppose that $a = 2^kb,$ where $b$ is odd. If $\phi(x) = a,$ prove that $x$ has at most $k$ odd prime divisors.
1
vote
1answer
438 views

Finding All Integers in such that $\phi(n)=80$

I don't know where to start with this problem so please help. The problem is: Find all integers n such that $\phi(n) = 80$.
1
vote
1answer
87 views

Erdős–Turan construction of Golomb ruler

The following equation produces a Golomb ruler for every odd prime p $$ 2pk + (k^2 \bmod p), \quad k\in[0,p-1] $$ and every two contiguous points has a unique difference. my question is how to get ...