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

learn more… | top users | synonyms

2
votes
1answer
56 views

Prove Euler's Theorem when the integers are not relatively prime

How can I prove Euler's Theorem: $$x^{\phi(m)+1} \equiv x \pmod m$$ is still true when $x$ is not relatively prime to $m$? Edit: when m=pq where p and q are distinct primes
12
votes
1answer
498 views

Can this interesting property be proven?

$$2^2+3^2+5^2+7^2+9^2+11^2=(17)^2$$ $$22^2+33^2+55^2+77^2+99^2+11^2=(143)^2$$ Also: $$22^2+33^2+55^2+77^2+99^2+121^2=(187)^2$$ $$222^2+333^2+555^2+777^2+999^2+1221^2=(1887)^2$$ ...
2
votes
1answer
21 views

A possible defining characteristic of primitive roots.

If $n$ is a primitive root $\bmod p$ ($p$ is an odd prime ) does there always exist a least residue $t$ such that $n^t \equiv t \pmod p$ ?
3
votes
1answer
36 views

How many distinct values of floor(N/i) exists for i=1 to N.

Say we have a function $F(i)=\text{floor}(N/i)$. Then how many distinct values of $F(i)$ will exist for all $0 \leq i \leq N$ e.g. We have $N=25$ then. $F(1)=25$ $F(2)=12$ $F(3)=8$ $F(4)=6$ ...
1
vote
2answers
51 views

Notation question: $\ll$

I was perusing http://mathworld.wolfram.com/HighlyCompositeNumber.html and saw the following at the end: Nicholas proved that there exists a constant $c_2>0$ such that $Q(x) \ll (\ln x)^{c_2}$. ...
1
vote
1answer
18 views

Cubic residues over $\mathbb{Z}_{p^2}^{*}$

Definition: $x\in\mathbb{Z}_{n}^{*}$ is a cubic residue if there exists $y\in\mathbb{Z}_{n}^{*}$ s.t. $y^3\equiv x \pmod{n}$. I have been asked to prove (and I already did) that if $n=pq$, ...
2
votes
1answer
20 views

Discrete logarithm when $\alpha$ is not a primitve root

When a number $\alpha$ is a primitive root for a prime number $n$ then $\beta \equiv \alpha^{x} \mod n$ can be written as $x = \log_\alpha(\beta) \mod n-1 $. If $n$ is not a prime, the equation ...
3
votes
3answers
44 views

Primitive roots of $25$

I'm kind of struggling with the concept of primitive roots with non primes, specifically for $25$ in this case. I was calculating the sequences $2^x \pmod {25}$ and $3^x \pmod{ 25}$ for each $x$ up to ...
11
votes
2answers
442 views

(Non?)-uniqueness of sums of squares

(I've had almost no exposure to number theory, so please keep answers as elementary as possible.) Write $\mathbb{N} = \{0,1,2,3,\ldots\}$ for the natural numbers. Then every element of $\mathbb{N}$ ...
-6
votes
1answer
61 views

Prove that $(a+b)/c = a/c + b/c$. [closed]

Prove that one can simplify a fraction to get a number and a fraction. I know this is obvious intuitively, but I'd like to see a formal proof. Thanks!
8
votes
0answers
41 views

Dividing first $n$ primes into two sets with equal sum

Let $N$ be a positive integer. Does there always exist $n>N$ such that the first $n$ primes can be divided into two sets with equal sum? If $n$ is even, the sum of the first $n$ primes is odd, so ...
8
votes
1answer
197 views

How to solve $y^2=3x^4+3x^2+1$ for integers.

If $x,y \in \mathbb Z$ , then find all the solutions of $$y^2=3x^4+3x^2+1$$ I was asked this question by my friend who said that he encountered this while solving another problem. I have ...
10
votes
1answer
29 views

Find all positive integers $n$ such that $\phi(n) + \tau(n) > n$. [duplicate]

How do I find all positive integers $n$ such that $\phi(n) + \tau(n) > n$? I attempted using the formulas for $\phi(n)$ and $\tau(n)$, but I feel this approach is kind of handwavy...
0
votes
1answer
24 views

Please help me evaluate this product involving logarithms.

Please help me evaluate this product: $$\prod _{n=0}^{\infty } -\frac{\log \left(-\frac{1}{6 n+2}\right) \log \left(-\frac{2}{6 n+3}\right) \log \left(-\frac{1}{6 n+4}\right) \log \left(\frac{1}{6 ...
2
votes
4answers
67 views

How many finite sequnces $x_1,x_2,x_3,\ldots,x_m$ are there such that $x_i =1$ or $2$ and $\sum_{i=1}^{m}x_i=10$ [closed]

How many finite sequnces $x_1,x_2,x_3,\ldots,x_m$ are there such that $x_i =1$ or $2$ and $\sum_{i=1}^m x_i=10$ A. $89$ B. $91$ C. $92$ D. $120.$
1
vote
1answer
26 views

Factoring $x^{3}-6\in \mathbb{F}_{p}[x]$ when $p\equiv 1$ mod $3$.

If $p\equiv 1$ mod $3$, I know that $x^{3}-6$ has any solution in $\mathbb{F}_{p}$ if and only if there exist $A,B\in\mathbb{Z}$ such that $p=A^{2}+3B^{2}$ and $9|B$ or $9|(2B+A)$ or $9|(2B-A)$ (This ...
2
votes
1answer
25 views

Find sum of possible pairs for given LCM and GCD

I am given $A$ and $B$. I have to find out sum of $(m+n)$ for all pairs of numbers where $m\leq n$, $\gcd(m,n)=B$ and $\operatorname{lcm}(m,n)=A$ For $A=72$, $B=3$ Possible pairs will be - $(3,72)$, ...
0
votes
1answer
45 views

Find smallest $x$ such that $a^x \equiv b \bmod p$

Problem: How do we find smallest $x$ such that $a^x \equiv b \bmod p$, where $p$ is a prime and $1 \le b,a \le p$ and $a$, $b$, and $p$ are given and fixed. If there is no such $x$, how do we check ...
3
votes
2answers
252 views

Is this a legitimate proof? If not, how to prove?

Question: Determine all natural numbers $n$ such that: $7 \mid \left(3^n - 2\right) \implies3^{n}\equiv 2\pmod{7}$ Multiply both sides by 7 $7 \cdot 3^{n}\equiv 7\cdot2\pmod{7}$ Divide both sides ...
4
votes
4answers
87 views

Determining the last two digits of $229^{10} +37^{10}$

Determine the last two digits of: $229^{10}+37^{10}.$ I do not want to use the Euler-totient function or the carmichael function please! Thanks
2
votes
2answers
91 views

Summing of factorials to produce perfect cubes

I was playing around with factorials the other day, and I realized that $4!+5!$ is a perfect square. Perplexed by this result, I started looking for other pairs of factorials that produce a perfect ...
2
votes
1answer
67 views

Find the greatest integer $N$ such that no two of its digits are equal and each digit is also its factor

$N$ is a positive integer such that no two of its digits are equal and each digit is also its factor. What is the largest value of $N$? So far, I've determined that $0$ cannot be the last digit, and ...
-1
votes
1answer
25 views

If $p\equiv 2$ mod $3$, $x^{3}\equiv a$ mod $p$ has only one solution modulo $p$.

Let $p$ be an odd prime and $a\in \mathbb{Z}$ such that $p\nmid a$. I have to show that if $p\equiv 2$ mod $3$, then $x^{3}\equiv a$ mod $p$ has only one solution modulo $p$. Using the properties of ...
0
votes
1answer
34 views

Prove homomorphism and surjectivity of a function

I have a question about this exercise for my math study: Let $d, n \in\mathbb{Z}_{>0}$ with $d\mid n$. a) Prove that there is a homomorphism $g: (\mathbb{Z}/n\mathbb{Z})^*\rightarrow ...
4
votes
2answers
91 views

Number of solutions of a simple equation

Problem How to count the number of distinct integer solutions $(x_1,x_2,\dots,x_n)$ of the equations like : $$|x_1| + |x_2| + \cdots + |x_n| = d $$ the count gives the number of coordinate points ...
2
votes
0answers
31 views

A question about a system of congruent equations? Is there a unified proof by using ring theory?

In his book ``Topics in number theory, Volumes I and II''. William J. Leveque proved the following theorem(see page 34) Theorem A necessary and sufficient condition that the system of congruences ...
1
vote
1answer
38 views

Greatest common divisor is divisible by every common divisor [duplicate]

Can anyone give a proof for the following elementary assertion without use of Bézout's theorem which says that The Greatest Common Divisor of two integers is an integer linear combination of them. ...
1
vote
2answers
40 views

How does this proof that the square of an integer, not divisible by 5, leaves a remainder of 1 or 4 when divided by 5 work?

Below I have a part of a proof of the fact that the square of an integer, not divisible by $5$, leaves a remainder of $1$ or $4$ when divided by $5$. But I am wondering where does the part highlighted ...
0
votes
2answers
41 views

How do I prove that $x^s=(-1)^k \sum_{k=0}^{(r-1)/2}\binom{r}{2k}p^{s(r-2k)}$ has no solutions?

I have been struggling to prove that the following diophantine equation has no integral solutions if $r$ is odd, $s,p>1$ $$x^s=(-1)^k \sum_{k=0}^{(r-1)/2}\binom{r}{2k}p^{s(r-2k)}$$ Any hint on how ...
12
votes
2answers
643 views

Evidence against Goldbach's Conjecture?

It recently occurred to me that, unless I'm much mistaken, Goldbach's conjecture can easily be seen to be equivalent to a seemingly more general statement: Every number $n$ divisible by any ...
3
votes
1answer
45 views

How many co-prime pairs are there between 1 and N?

I suspect it's $$n^2 - \sum_{i=1}^n \phi(i) + 1$$ with $\phi(i)$ being the Euler function for the number of co-primes to $i$ between $1$ and $i$. But I have absolutely no proof to this but for example ...
2
votes
1answer
58 views

Show that there are at least $2$ elements in $U(n)$ such that $x^2=1$.

I am working on some exercises in Joseph Gallian's Contemporary Abstract Algebra. I came upon the following: Show that there are at least $2$ elements in $U(n)$ such that $x^2=1$, for $n>2$ ...
2
votes
1answer
24 views

Solve the congruence $x^2=x \mod (2 \cdot 3)^2. $

How to solve the congruence $x^2=x \mod (2 \cdot 3)^2? $ Using brute forse it is easy to show that $x=0,1,9,28.$ But how to get the result by calculation?
1
vote
0answers
25 views

Unique Solution To The Diophantine Equation

Show that the following Diophantine equation has a unique solution in positive integers $x^n+y^n=(x+y)^m$ with $x>y, m>1,n>1$. This could be solved by a direct use of Zsigmondy's theorem. ...
0
votes
0answers
29 views

How to prove a congruent to b (mod n) is a bijection?

I can prove it's an equivalence relation, but NO idea how to prove it's a bijection. I know I need to prove it's surjective/injective, but how do I establish it to even be a function?
0
votes
0answers
23 views

Is subtraction a binary operation on $S$

According to what I have been instructed before seeing this question, am suppose to subtract these number until I obtain a set of numbers that are non-negative and all less than 6.I am trying to ...
1
vote
0answers
25 views

Show Equivalence of Binary Quadratic Forms

I've been stuck on these two problems from my problem set for quite a while. Any help would be appreciated! 2)Suppose that $ax^2 + bxy + xy^2$ is equivalent to $Ax^2 + Bxy + Cy^2$. Show that $gcd ...
-2
votes
0answers
27 views

Congruence modulo numbers together [closed]

Please, help me solve this equation: $x^{17386} \equiv 43927 \;(\bmod\; 64349)$ Thanks. Regards.
-2
votes
10answers
147 views

Show that the number $n$ is divisible by $7$ [duplicate]

How can I prove that $n = 8709120$ divisible by $7$? I have tried a couple methods, but I can't show that. Can somebody please help me?
0
votes
2answers
45 views

a question about relatively prime numbers

Is it true that if $m, n$ are relatively prime integers, then $mn$, $m-n$ are also relatively prime? It seems intuitively true but I can't prove it... Could anyone help me how to prove it?
4
votes
2answers
57 views

Find minimum of $a+b$ if $13|a+11b $ and $11|a+13b$

Find minimum of $a+b$ if $13|a+11b $ and $11|a+13b$ where $a,b>0$. My attempt : $13|a+11b \implies 13|a+24b$ . Similarly we get $11|a+24b$. Now $\gcd(11,13)=1$, so, $143|a+24b$. Therefore $a+24b ...
6
votes
1answer
121 views

Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
3
votes
0answers
38 views

Trying to prove a congruence for Stirling numbers of the second kind

I am struggling with a demonstration for this: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace ...
3
votes
4answers
51 views

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$. Hello. I am working on a review sheet for my test tomorrow and I am stuck on this ...
10
votes
7answers
924 views

Prove by induction that an expression is divisible by 11

Prove, by induction that $2^{3n-1}+5\cdot3^n$ is divisible by $11$ for any even number $n\in\Bbb N$. I am rather confused by this question. This is my attempt so far: For $n = 2$ $2^5 ...
2
votes
2answers
36 views

Show that $ p^{(q-1)} + q^{(p-1)}$ is congruent to $1 \hspace{1mm } ($mod $ pq)$

Same review sheet, sorry for posting so much. But any help is appreciated. Let $p$ and $q$ be distinct prime numbers. Show that $p^{(q-1)} + q^{(p-1)} \equiv 1 \hspace{1mm } ($mod $pq)$. (hint: ...
2
votes
1answer
57 views

Number of solutions of $3x^2 - 5x + 3\equiv 0 \pmod{m}$?

I'm asked, for each of the following values of $m$, to find the number of solutions (in the set $Z_m$) of the quadratic congruence $3x^2 - 5x + 3\equiv 0 \pmod{m}$. For $m=53$ $m=73$ ...
8
votes
2answers
418 views

Let $a=43120$ How many positive divisors does a have?

I am doing a review assignment and I'm stuck on this problem. a) How many positive divisors does $a$ have? I got $60$ b) How many positive integers less than $a$ are relatively prime to $a$? I got ...
1
vote
0answers
88 views

Counting arrays problem [closed]

Given N, M and D I need to count how many sequence of N elements a[1],a[2].....a[n] can be formed which satisfy these 2 conditions : Each element is between 1 ≤ Ai ≤ M. Greatest common divisor of ...
1
vote
1answer
53 views

Find the residue of $1!+2!+…+n! \pmod{m}$ for $m>n$

Find the residue of $ 1!+2!+........+n! \pmod{m}$ for $m>n$ $n,m$ are positive numbers and need not be primes. is there any known proof or result for this thanks