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

learn more… | top users | synonyms (1)

-3
votes
0answers
33 views

few elementary questions in Number Theory

I have a few questions in Number Theory: if $a​≡k^2$ and $gcd (a,p)=1$ then is $gcd(k^2, p)=1$? when can I "divide" a congruence and say that it is equivalence to the original congruence? for ...
-1
votes
2answers
36 views

Prove that $(\mathbb Z/m\mathbb Z)^\times$ is cyclic if and only if there is a primitive root modulo $m$

Prove that $(\mathbb Z/m\mathbb Z)^\times$ is cyclic if and only if there is a primitive root modulo $m$. if $g$ is a primtive root modulo $m$ so indeed $(\mathbb Z/m\mathbb Z)^\times$ is cyclic by ...
1
vote
2answers
31 views

Problem in proof of: Show that inverse of 'a' modulo 'm' exist if 'a' and 'm' are relative primes and 'm'>1?

From K Rosen's Discrete Maths, Theorem: If a and m are relatively prime integers and m > 1, then an inverse of a modulo m exists. Furthermore, this inverse is unique modulo m. (That is, there is a ...
1
vote
0answers
75 views

Any natural number n can be expressed as $n = 2^a \cdot b$ where $b$ is odd. Function such that $f(n) = a$

Given that any natural number $n$, can be expressed $n = 2^a \cdot b$ where $b$ is odd. Is there a function that does not include modulo or floor functions that satisfies $f(n) = a$? Thus far I have ...
0
votes
0answers
6 views

Exponential sum over $(\mathbb{Z}/(p^t))^*$

Let $p$ be a prime and $t$ a natural number. Let us denote $(\mathbb{Z}/(p^t))^*$ to the group of units of $\mathbb{Z}/(p^t)$. I have the following exponential sum $$ S = \sum_{w \in ...
13
votes
3answers
1k views

How to solve this algorithmic math olympiad problem?

So, today we had a local contest in my state to find eligible people for the international math olympiad "IMO" ... I was stuck with this very interesting algorithmic problem: Let $n$ be a natural ...
0
votes
3answers
33 views

Which is not a primitive root?

If p is an odd prime then $6$, $10$ and $15$ cannot all be primitive roots. My question is this: Why can't all three (simultaneously) be a primitive root modulo $p$? I have no idea why this is the ...
3
votes
2answers
57 views

Prove that if $2n+1$ and $3n+1$ are both perfect squares then $40|n$.

Prove that if $2n+1$ and $3n+1$ are both perfect squares then $40|n$. First, I took $$2n+1 \equiv x^2 \equiv 0, 1 \pmod 4$$ which showed that $n$ was even. Now, $$3n + 1 \equiv y^2 \equiv 0, 1, ...
3
votes
1answer
29 views

If for $p \in \Bbb P$ and $x,y,z \in \Bbb N$ we have $x^{p-1}+y^{p-1}=z^{p-1}$, then $p\mid xyz$

I want to prove the statement in the title. This is, how far i came: Proof. We have $p \in \Bbb P$ and $x,y,z \in \Bbb N$ with $x^{p-1}+y^{p-1}=z^{p-1}$. If $p=2$, we have $x+y=z$. Now if $x$ and ...
0
votes
0answers
13 views

numbers x such that the sum of the divisors is a perfect square [duplicate]

Hello I am reading "The Theory of Numbers, by Robert D. Carmichael" and stuck in an exercise problem, Find numbers x such that the sum of the divisors of x is a perfect square. I know sum of ...
0
votes
0answers
23 views

Find all pairs positive integers $m,n>1$, such that $(mn-1)|(n^3-1)$ [duplicate]

Find all pairs of positive integers $m,n>1$, such that $$(mn-1)|(n^3-1)$$ My work so far: 1) If $m=n^2$, then $(mn-1)=(n^3-1)|(n^3-1)$. Then $(m,n)=(n^2,n) -$ solution. 2) $(mn-1)|(n^3-1) ...
1
vote
1answer
21 views

How many positive pairof integral values (x,y) exist which satisfy $2xy-4x^2+12x-5y=11?$

How many positive pairof integral values (x,y) exist which satisfy $2xy-4x^2+12x-5y=11?$ My attempt: $y=(4x^2-12x+11)/(2x-5)=\dfrac{(4x^2-10x)-(2x-5)+6}{2x-5}=2x-1+6/(2x-5)$ For any such pair ...
-1
votes
2answers
48 views

Does there exist an integer $x$ satisfying the following congruence: [duplicate]

Does there exist an integer $x$ satisfying the following congruence: $10x=1\mod 21$ $5x=1\mod 6$ $4x=1\mod 7$ My try: Using Chinese Remainder Theorem: $n=n_1*n_2*n_3=21*6*7=882$ . Then consider ...
0
votes
2answers
36 views

Factor the number $2^{11} - 1$ by fermat's factorization method

I started with finding the smallest integer k such that $k^2 - (2^{11} - 1) >= 0$. But then I need the smallest j where j = $2^6$, $2^6+1$, ... ,$\left(\frac{(2^{11}-1+1)}{2}\right)^2$ Such that ...
3
votes
2answers
52 views

Diophantine $xy+yz+zx=4(x+y+z)$

How do you solve the Diophantine equation $xy+yz+zx=4(x+y+z)$ for positive integers $x,y,z$? My approach was to consider $d=\gcd(x,y,z)$. I could just about show that the equation has no ...
2
votes
2answers
45 views

Perfect square ending with $1$'s and $2$'s

Is it true that for any $n$, there exists a perfect square whose last $n$ digits are only $1$ or $2$? For example we have $1^2=1$, $11^2=121$, $511^2=261121$. But $111^2=12321$, so we cannot just use ...
2
votes
1answer
82 views

A number is prime if and only if …

Prove that a number $p$ is prime if and only if the $\gcd(\text{numerator},\text{denominator})$ of all fractions of the form $$\frac{1}{p - 1}, \frac{2}{p - 2}, \frac{3}{p - 3}, \ldots, \frac{k}{p - ...
1
vote
2answers
36 views

Minimizing the intersection of three sets

Let the sets $A,B,C$ which are all subsets of a larger set $N$. If $N(A), N(B), N(C), N$ are the populations respectively, then i need to find the minimum value of the population of their intersection ...
2
votes
2answers
90 views

Is $\frac{1010103010101}9$ prime or composite?

$1010103010101$ obviously divisible by $9$. Is $\frac{1010103010101}9$ prime or composite? The answer would be obtained without using WolframAlpha
0
votes
0answers
19 views

The numbers appearing in the simple continued fraction

The numbers appearing in the simple continued fraction expansion for sqrt(n) when n is non-square has 2 neat properties. What are they?
0
votes
0answers
26 views

Periodicity of the continued fraction of a square root

Writing $\sqrt{n}=[a_0; a_1, a_2, \dots ]$, at which $a_i$ does the period start? Is it $a_1$? I just put "for some $n\ge 1$, where $a_{n-1}=a_i$", is that a good enough answer?
0
votes
4answers
104 views

Why isn't 1900 a leap year? [closed]

I searched leap years online and found that 1900 is not, contrary to what I thought, a leap year. But, why is it not if 1900 is divisible by 4: $\frac{1900}{4} = 475$ My brother was working on his ...
1
vote
2answers
35 views

How to calculate $x$ in $19^{93}\equiv x\pmod {162}$?

I have to calculate $19^{93}\equiv x\pmod {162}$. All I can do is this,by using Euler's Theorem:- $19^{\phi(162)}\equiv1\pmod{162}$ So,$19^{54}\equiv1\pmod{162}$ Now,I have no idea how to reach ...
1
vote
2answers
41 views

Prove that $p|1+2(p-3)!$

Prove that $p|1+2(p-3)!$ I know the wilson's theorem and started with that but I reach a stage where I am not able to solve. $1+(p-1)!= M(p)$ $=1+(p-1)(p-2)(p-3)!= M(p)$ $=1+ (p^{2}-3p+2)(p-3)! ...
1
vote
2answers
142 views

Why $82000$? Numbers that can be written from base $2$ to base $5$ using only the digits $0$ and $1$

This is really very curious. Many links on http://oeis.org/A146025 about this but -- why? I mean, this is not some abstract mathematical notation but rather something inherent in, I dunno, the ...
5
votes
3answers
175 views

What is the optimal strategy in a game where players subtract 7 or add or divide by 2?

I made up a nim type game where players start with a relatively high number and then for each turn if the number is odd, the player either subtracts 7 from the number or alternately if the number is ...
4
votes
1answer
28 views

Show that $2k\choose k$ divides the lcm of $1, \dots, 2k+1$

I want to show that $(2k+1){2k\choose k}$ is a factor of $\text{lcm}(1, \dots, 2k+1)$. Clearly the divisor is equal to $2^k\frac{1\cdot3\cdot\dots\cdot (2k+1)}{k!}$, but I don't know how to show that ...
3
votes
2answers
57 views

Given $x^3$ mod $55$, find its inverse

So i am wondering how i can figure out what the functional inverse of $x^3$ mod $55$ is. I can only assume it is $x^{1/3}$ mod $55$ but i am not sure if that is the form i should keep it in
2
votes
3answers
95 views

If $ab^2+1 = c^2+d^2$ with $a$ squarefree, what [else] can be said about $a$?

What is known about squarefree integers $a$ where there exist non-zero integers $b$, $c$, and $d$, with $\gcd(b,c)=\gcd(b,d)=1$, such that $$ab^2+1=c^2+d^2$$ ? EDIT: As pointed out by individ, if an ...
0
votes
1answer
29 views

If $d = (a, b)$ and $a=da_1$, $b=db_1$, show that $(a_1, b_1)=1$. [duplicate]

First off, the problem states that $d$ is the GCD of $a$ and $b$ and $a_1$ and $b_1$ are integers. Now I tried putting them in a linear combination such that it would look like $da_1x+db_1y=d$. Well ...
10
votes
0answers
87 views

Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all ...
2
votes
0answers
29 views

Let $N=3^{1000}\times 2^{200009} +1$. Show that $5^{\frac{N-1}{2}}\equiv -1 \pmod{N}$.

This is showing that 5 is a quadratic non-residue mod N but I don't get why this says it is prime. The question also asks that you say that if p was prime divisor of N what the power of 2 dividing ...
0
votes
0answers
56 views

solution of the Pythagorean triple (a,b,21025)

I know that most intelligent people on this site will find this elementary question very simple (I hope you'll forgive me, I'm not yet familiar enough with mathematics): What is the solution of ...
0
votes
0answers
56 views

Number of solutions to a modular equation of a specific form

I struggle with this Exercise, or at least the part where one should prove how many solutions there are. Simply inserting f=0 contradicts the suggested number of solutions. Let $p$ be an odd ...
0
votes
0answers
26 views

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite?

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite? Is there a general way to determine the number of ...
0
votes
0answers
23 views

Number of solutions to $f(x)\equiv 0 \mod(11\cdot 19^{2})$

I have been asked to explain why the number of solutions of the polynomial congruence $f(x)\equiv 0 \mod (11\cdot 19^{2})$ cannot be 121, where $f(x)=x^{10}+10x^{8}-17x+12$. Any ideas?
2
votes
1answer
34 views

If $p$ is an odd prime show that $2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$

If $p$ is an odd prime show that $$2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$$ This is an exercise from Elementary Number Theory, 2nd Edition by Underwood Dudley. I know that the expression ...
2
votes
2answers
63 views

Find triples $(a,b,c)$ of positive integers such that…

Find the triples $(a,b,c)$ of positive integers that satisfy $$\left(1+\frac{1}{a}\right)\left(1+\frac{1}{b}\right)\left(1+\frac{1}{c}\right)=3. $$ I found this on a local question paper, and I am ...
1
vote
1answer
19 views

Is a divides infinitely many repunits?

Let (a,10)=1 Let n=9k{phi(a)} using eulerphi function k is positive integer. When (a,9)= 1 , 3 it is okay Because 81 and a divides 10^n-1 by Binomial theorem and CRT So a divides (10^n-1)/9 ...
0
votes
0answers
12 views

Proof $\forall n \in \Bbb N$ that $2^n \cdot \prod_{i = 1}^{n} (2i-1)$ is divisible by $n!$

I'm trying to prove it by induction. $P(1)$ holds true. My inductive hypothesis is $n!\ |\ 2^n \frac {2n!} {2^n n!}$ which simplifies to $n!\ |\ \frac {2n!} {n!}$. Next $P(n+1)$: $$(n+1)!\ |\ 2^{n+1} ...
2
votes
1answer
50 views

Find all integer values of $x$ such that $x^2 + 13x + 3$ is a perfect integer square.

Question: Find all integer values of $x$ such that $x^2 + 13x + 3$ is a perfect integer square. What I have attempted; For $x^2 + 13x + 3$ to be a perfect integer square let it equal ...
2
votes
1answer
32 views

If $p>5$ is prime, $2p+1$ is a prime, $\frac{4p+1}{3}$ is prime, $8p+1$ is prime, Then $p \equiv 29 (mod \; 30)$

Assume that $p>5$ is prime, $2p+1$ is a prime, $\frac{4p+1}{3}$ is prime, $8p+1$ is prime. Then I want to prove that $p \equiv 29 (mod \; 30).$ First of all I have to show that $4p+1$ is a ...
1
vote
1answer
43 views

Smallest positive integer r such that $8^{17} \equiv r \pmod {97}$

I want find out the Smallest positive integer r such that $8^{17} \equiv r \pmod{97}$. Fermat's theorem only tells us $8^{96} \equiv 1 \pmod{97}.$ How can I proceed. Any hint will be appreciated. ...
1
vote
0answers
13 views

Integer division and congruence exercise

I'm just starting with integer division and congruence in an algebra course and I have this problem: Let $a$ be an odd integer. Prove that $\forall n \in \Bbb N$: $$2^{n+2}\ |\ a^{2^n} - 1$$ I've ...
2
votes
1answer
14 views

Boundedness of set with function on prime divisors

Let $P(n)$ denote the product of the prime divisors of $n$, e.g., $P(100)=2\times 5=10$. Define $$A=\{\frac{a}{P(ab(a-b))} \mid a,b\in\mathbb{Z}^+, a>b\}.$$ Is $A$ bounded or not? To make the ...
1
vote
2answers
78 views

A prime number problem.

If $n$ is a positive integer and $(p_1,p_2,p_3,p_4,\ldots, p_n)$ are distinct positive primes, show that the integer $(p_1\cdot p_2\cdot p_3\cdot p_4\cdots p_n)+1$ is divisible by none of these ...
1
vote
1answer
17 views

Reference for table of cubes modulo $m$?

Is there an online table with all the cubes in $(\mathbb{Z}/m\mathbb{Z})$ (with $m$ up to (say) $100$, at least)? I didn't find anything googling it. Thanks.
0
votes
0answers
12 views

Which of a,b,c,d is/are odd given the set of conditions?

I am trying to answer this question. Which of a,b,c,d is/are odd given the set of conditions? Condition 1.) ad + bc is odd Condition 2.) ac + bd is odd The question is actually asking if we can ...
0
votes
1answer
23 views

Help with congruence and divisibility exercise

I'm starting to solve some problems of congruence and integer division, so the exercise is quite simple but I'm not sure I'm on the right track. I need to prove that the following is true for all $n ...
3
votes
2answers
56 views

if $p\mid a$ and $p\mid b$ then $p\mid \gcd(a,b)$

I would like to prove the following property : $$\forall (p,a,b)\in\mathbb{Z}^{3} \quad p\mid a \mbox{ and } p\mid b \implies p\mid \gcd(a,b)$$ Knowing that : Definition Given two ...