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

learn more… | top users | synonyms

0
votes
1answer
46 views

Finding solutions to equations in $Z_{143}$

How would you find all solutions to the equation $x^2=3$ in $Z_{143}$? I don't really know where to start.
0
votes
2answers
130 views

$9n^2-4$ only generates one prime? Why?

Instead of doing the work I was supposed to be doing, I played around with some numbers, and I noticed that for $n\in\mathbb{N}$, $9n^2-4$ only seems to generate a prime for $n=1$. Can anyone ...
0
votes
4answers
112 views

Is at least one of $6k + 1$ or $6k-1$ prime?

We know that any prime number ( $> 2,3$) can be written in the form $6k+1$ or $6k-1$. Is it necessary that at least one of $6k+1$ or $6k-1$ is a prime number ?
2
votes
2answers
32 views

Using modular arithmetic to find$ [2^{16}]_8$…

This is a fairly simple problem. Just wanted to check if there's another method that I should of used. Here goes--- The problem: Find $2^{16} \mod 8$ So I figured this one out pretty quickly, ...
1
vote
0answers
22 views

Elementary Application of Legendre Symbol [duplicate]

For odd primes $p,q$ with $p\equiv q\pmod{4a}$, then how can we show that $a$ is a quadratic residue $\mod p$ if and only if it is a quadratic residue $\mod q$ using legendre/jacobi symbols?
2
votes
1answer
52 views

need help in number theory problem

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
0
votes
1answer
39 views

If $x$ is an integer and $x \ge 5$, then there's $y$ such that $x + y$ is a perfect square with $x > y$.

$y < 5 \le x$ by hypothesis. Let $y = -x$. Then, $-x + x = 0$. Since $0$ is a perfect square, we are done. I am not sure if this proof would fly. Please, tell me what you think.
1
vote
1answer
62 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
-1
votes
1answer
39 views

Who will be last [closed]

There are n children in school and teacher is going to give some candies to them. Let's number all the children from 1 to n. The i-th child wants to get at least a[i] candies. Teacher asks children ...
1
vote
2answers
41 views

Show that if $a^h ≡ 1\mod p$ then $ a^{ph} ≡ 1 \ \mod p^2$.

I don't know how to proceed. I know that regardless of what h is, it divides the order of a modulo $p$. I also know that the order of a divides $\phi(p) \ \text{mod} \ p$, where $\phi$ is Euler's ...
8
votes
10answers
192 views

Prove $n^4 \equiv 1 \pmod{5}$

Suppose $n$ is an integer which is not divisor of 5. Prove that $n^4 \equiv 1 \pmod{5}$. I tried saying that $n$ is not equal to 5 or 1, thus $n$ must divide $2 \times 3 \times 4 = 24$. I am stuck at ...
0
votes
2answers
40 views

Need help finding a number x so that $\phi > 9x/10$?

I need help finding a number $x$ so that $φ(x) > 9x/10$? ($φ$ being Euler’s phi function.) I also need to find a number $x$ so that $φ(x) < x/3$?
2
votes
2answers
47 views

Proving this corollary of the Unique Factorization Theorem (of Integers)…

Here's the Corollary in it's entirety Corollary 1.3.5 (from Numbers, Groups, and Codes by J.F. Humphreys) Let $a,b \in \mathbb{Z^+}$ and let $$a=\prod_{i=1}^r p_i^{n_i}$$ ...
0
votes
3answers
39 views

x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences?

Say, x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences? I am worried this question is too easy to be true. That is why I am confused. ...
4
votes
3answers
61 views

Rational number trivial case

Let $a,b,c$ denote rational numbers, such that $(a+b\sqrt[3]2+c\sqrt[3]4)^3$ is also rational. Prove that at least two of the numbers $a,b,c$ must be zero. Actually I confused of the beginning steps ...
0
votes
1answer
46 views

Congruence and percentage

Suppose I have three statements of congruence: x = a mod n, y = b mod m, z = c mod p; Furthermore, x is a given percent of x + y + z, as is y and z. Does this uniquely determine x, y, z? Or does it ...
0
votes
0answers
21 views

Number solutions of congruence

Let $f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$ and $f(x)\equiv 0 \pmod p$ have more than $n$ solutions. Then $p\mid a_i$ for $i=0,1,\dots,n$. My proof: Let $m$ be the maximal such that $p\nmid a_m$ ...
2
votes
1answer
30 views

Integer condition and perfect square relation

Suppose $a,b,c,d$ are integers such that $a+b+c+d$=0. Prove that $2a^4+2b^4+2c^4+2d^4+8abcd$ is a perfect square. I eliminated $a,b,c,d$, then the steps went lengthy and I could not concretise
0
votes
0answers
45 views

Fast check of safe primes or Sophie Germain primes

If $p=2q +1$ with $p,q$ prime then $p$ is called safe prime and $q$ is a Sophie Germain prime. I want a faster algorithm for a safe prime test than doing two primality checks for $p$ and $q$. In ...
3
votes
0answers
53 views

Is there a positive integer $N$ that fits? [duplicate]

Is there a positive integer $N$ such that the equation $x^2 + y^2 = N$ has at least $2005$ solutions in non-negative integers $x$ and $y$? If so, prove it. If not, prove it!
1
vote
3answers
30 views

Perfect squares and modularly congruency in mod 5

There is not any perfect square $k$ such that $k \equiv 3\ (\textrm{mod}\ 5)$? Why? How can I prove it?
2
votes
5answers
29 views

Proving that $nb \text{ (mod m)}$ reaches all values $\{0 \dots (m-1)\}$ if $n$ and $m$ are relatively prime

I am trying to prove the frobenius coin problem which requires me to prove the following lemma: If $n$ and $m$ are relatively prime and $b$ is any integer, then the set of all possible values of $$nb ...
2
votes
2answers
127 views

Counting the number of digits in a concatenation

Concatenate the numbers $2^{1971}$ and $5^{1971}$. How many digits are there in the new number? How do I count them?
1
vote
0answers
27 views

Is there a positive integer base of numeration for which no equivalent of Benford's law holds?

Obviously a trivial equivalent of Benford's law holds in binary. In trying to narrow it down, I thought about looking at just prime numbers, which maybe tells me nothing because some people say the ...
2
votes
1answer
83 views

Prime number upper bound

I am reading some written notes about a proof I do not understand, maybe some informations are missing. The result that has to be proved is the following: if $p_n$ is the $n$-th prime number, ...
6
votes
4answers
73 views

$k$-th number in $N \times M$ Table

Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in ...
1
vote
1answer
55 views

factoring polynomials in $\Bbb Z/11\Bbb Z$

Any ideas as in how to Factor $x^{10}-1$ into linear factors in the integers modulo $11$, $\Bbb Z_{11}=\Bbb Z/11\Bbb Z$? I've been trying but can't come up with an answer.
0
votes
2answers
22 views

A simple query on index of positive real numbers

If $a$ and $b$ are any two non-negative real numbers, then I just want to know the validity of the statement $\bf a<b\implies a^p<b^p$ in terms of real positive values of $p.$
2
votes
2answers
160 views

Prove that for any give sequence of digits, there is a perfect square starting with that sequence

Prove that for any give sequence of digits, there is a perfect square starting with that sequence. With more details, prove that for $\forall a\in \mathbb{N}$, such that ...
5
votes
1answer
115 views

Combinations mod $n$ property

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense): $\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n ...
3
votes
1answer
112 views

Remainder of $\frac{x^{60}+x^{48}+x^{36}+x^{24}+x^{12}+1}{x^{5}+x^{4}+x^{3}+x^{2}+x+1}$

I am trying to find the remainder of the polynomial division $$\frac{x^{60}+x^{48}+x^{36}+x^{24}+x^{12}+1}{x^{5}+x^{4}+x^{3}+x^{2}+x+1}$$ I know that the answer is 6, but I am not getting that when I ...
0
votes
5answers
108 views

Show the $(p-1)! \equiv -1 \mod p/$…

Okay so the full problem as stated is: Let $p$ be a prime number. Show that $$(p-1)! \equiv -1 \mod p.$$ I attempted to use induction, where we let p=2 be our base case then consider all primes ...
1
vote
1answer
37 views

How can i prove that a cartesian product is isomorphic to another cartesian product

$\def\<#1>{\left<#1\right>}\def\Z{\mathbb Z}\<\Z_6, \oplus> \times \<\Z_{10},\oplus>$ is isomorphic to $\<\Z_2, \oplus> \times \<\Z_{30}, \oplus>$ i know i have to ...
0
votes
0answers
21 views

Complete residue mod $p$ and number of solution to an equation

Prove that there are infinitely many primes $p$ such that the total number of solutions $\pmod{p}$ to the equation $3x^{3}+4y^{4}+5z^{3}-y^{4}z \equiv 0$ is $p^2$. I can show that for $p \equiv ...
1
vote
1answer
55 views

Calculating a Factorial Base Representation

My friend thought of a system in which each number $n$ (I will first restrict my question to positive integers $n$) is represented by a digit string $(d_l,...,d_1)$ as follows $\forall n \in ...
7
votes
2answers
204 views

Find all positive integers $n$ such that sum of digits of $2^n$ is equal to $n$.

For example, $2^5=32$ and $3+2=5$. Similarly, it can be shown that it works for $2^{70}$. Using basic results in modular arithmetic, one can show that $n$ has to be either of the form $18k+5$ or ...
7
votes
2answers
268 views

Is $7^{8}+8^{9}+9^{7}+1$ a prime? (no computer usage allowed)

Prove or disprove that $$7^{8}+8^{9}+9^{7}+1$$ is a prime number, without using a computer. I tried to transform $n^{n+1}+(n+1)^{n+2}+(n+2)^{n}+1$, unsuccessfully, no useful conclusion.
2
votes
2answers
103 views

Number of roots of polynomials in $\mathbb Z/p \mathbb Z [x]$

I was given this proposition but I was never able to prove it. Does anyone know how to solve this? Let $f$ be a polynomial in $\mathbb{Z}/p\mathbb{Z}[x]$, where $p$ is prime. Then $f$ has at most ...
3
votes
2answers
128 views

geometric methods in number theory

I was given this problem but I have no idea how to prove it. Any ideas? Let $n$ be a positive integer. The number of positive integral solutions to $\frac{1}{n}$ = $\frac{1}{x}$ + $\frac{1}{y}$ is ...
0
votes
1answer
65 views

number theory proofs with units, orders, and the phi function

How do you prove the following? : There exists some $u \in (\mathbb{Z}/n\mathbb{Z})^\times$ such that for all $v \in (\mathbb{Z}/n\mathbb{Z})^\times$, $\mathrm{ord} v \mid \mathrm{ord} u$. If the ...
1
vote
1answer
29 views

Perfect square and divisibility condition

If $x,y,z$ are integers such that $x^2+y^2=z^2$, prove that one of $x,y$ is divisible by 3 I tried conversely by expressing $x=3*q+r $ but I could not arrive at the proof
2
votes
1answer
26 views

Ramanujan type sum

Let $$f_b(x)=\sum\limits_{a=1 , (a,b)=1}^{b}\frac{1}{1-e^{2\pi i \frac{a}{b}}x}$$ For example: $$f_6(x) = \frac{1}{1-e^{2\pi i \frac{1}{6}}x}+\frac{1}{1-e^{2\pi i \frac{5}{6}}x}$$ I'm wondering if ...
3
votes
2answers
268 views

if $x_{n+1}=ax_{n}+b$ then How find this $a,b,c$?

Question: Let there be a sequence $x_{n}$ such that $$x_{n+1}=ax_{n}+b,,x_{1}=c$$ where $a,b$ and $c$ are positive integers. Suppose, too, that for $n,m\in \mathbb{Z^{+}}$ we have that $$ ...
3
votes
7answers
58 views

Suppose that $m \ge 0$ show that $49 \mid 5\cdot3^{4m + 2} + 53\cdot2^{5m}$

I've re-written the equation in a few different ways hoping for a few different approaches: $$49y = 5 \cdot 3^{4m + 2} + 53 \cdot 2^{5m} $$ I think the first equation has more potential, since it ...
0
votes
1answer
64 views

Equations modulo $143$

Let $x=11$ and $y=13$, and $z=xy=143$. (i) Show that $1$, $x+1$, $−1$ and $−(x+1)$ are the $4$ solutions of $n^2 \equiv 1\pmod z$. (ii) Find the coset of $U_z(2)$ consisting of solutions to $n^2 ...
1
vote
3answers
69 views

Number theory proofs relating to divisors [closed]

How do you prove this? $$\left(n-1\right)^2\mid\left(n^k-1\right)\Longleftrightarrow\left(n-1\right)\mid k$$
1
vote
3answers
79 views

Number theory proofs regarding perfect squares [closed]

How do you prove that $3n^2-1$ is never a perfect square
3
votes
2answers
28 views

Let $p$ be a prime of the form $3k+2$ that divides $a^2+ab+b^2$ for some integers $a,b$. Prove that $a,b$ are both divisible by $p$.

Let $p$ be a prime of the form $3k+2$ that divides $a^2+ab+b^2$ for some integers $a,b$. Prove that $a,b$ are both divisible by $p$. My attempt: $p\mid a^2+ab+b^2 \implies p\mid ...
3
votes
2answers
51 views

Let $x,y,z$ be positive integers such that $\frac{1}{x}-\frac{1}{y}=\frac{1}{z}$. Let $h=\gcd(x,y,z)$, Prove that $hxyz,h(y-x)$ are perfect squares

Let $x,y,z$ be positive integers such that $\frac{1}{x}-\frac{1}{y}=\frac{1}{z}$. Let $h=\gcd(x,y,z)$, Prove that $hxyz,h(y-x)$ are both perfect squares. My attempt: Let $x=ha,y=xb,z=xc$, then ...
1
vote
4answers
113 views

$7^n-1$ is divisible by $6$ for all natural number $n$ [closed]

How to prove $7^n-1$ is divisible by $6$ for all natural number $n$. Thanks for your help.